37
$\begingroup$

The built-in FindShortestPath and GraphDistance functions find the shortest path between two particular vertices in a graph. I can't think of a simple way to finding all shortest paths between two vertices. Any ideas?

My graph has weighted edges and the weights are arbitrarily large, so I'm dead against mapping weighted edges to many unweighted edges.

Motivation: I have a graph of city traffic routes from point A to point B. I'd like to take the union of shortest paths from A to B to get a subgraph that, I posit, contains (many of) the most frequented intersections.

$\endgroup$
15
  • 1
    $\begingroup$ @ruebenko: How would you apply Nearest to this problem? $\endgroup$
    – celtschk
    Apr 11, 2012 at 9:01
  • 1
    $\begingroup$ There is similar question stackoverflow.com/questions/2819347/… . The third answer is not a bad idea. $\endgroup$ Apr 11, 2012 at 9:09
  • 3
    $\begingroup$ The documentation for BreadthFirstScan has an example of this problem under Examples-Applications-Shortest Path Applications. $\endgroup$ Apr 11, 2012 at 9:31
  • 2
    $\begingroup$ Thinking about it, to get the union of shortest paths you probably don't need the set of shortest paths. I think the following algorithm should give you the union: Step 1: For each node, calculate the graph distance both to the start vertex A and the destination vertex B (let's call those values the A-distance and B-distance of that vertex). Step 2: Remove all edges whose weight is not both the difference between the A-distances of the vertices it connects and the difference between the B-distances. If I'm not wrong, the resulting graph should be exactly the union of all shortest paths. $\endgroup$
    – celtschk
    Apr 11, 2012 at 9:43
  • 2
    $\begingroup$ @SimonWoods The example with BreadthFirstScan works for very small toy problems but even for GridGraph with dimension $12 \times 14$ memory consumption increases with out bound. $\endgroup$ Apr 11, 2012 at 9:57

4 Answers 4

19
$\begingroup$

Directed Shortest Paths

Here's a friendly amendment to Heike's solution that shows the distance remaining to the finish vertex (in white). The starting vertex is green. Edges are directed to show the appropriate direction toward the finish. According to the documentation on GraphDistance, "For a weighted graph, the distance is the minimum of the sum of weights along any path between s and t." So it should automatically work with weighted graphs.

First, here's Heike's routine, which does most of the heavy lifting, with a simple tweak to produce directed edges:

paths[gr_, {i_, j_}] := 
  Module[{sub, dist, indices, dd, nbrs}, dist = GraphDistance[gr, i, j];
  indices = {};
  dd = dist;
  Reap[Nest[Function[{vv}, dd -= 1;
  nbrs = VertexList[NeighborhoodGraph[gr, #]] & /@ vv;
  nbrs = Pick[#, GraphDistance[gr, #, j] & /@ #, dd] & /@ nbrs;
  Sow /@ Flatten[Thread /@ Thread[vv \[DirectedEdge] nbrs]];
  Union[Flatten[nbrs]]], {i}, dist]][[2, 1]]]

The following produces the directional routes. Numbers refer to GraphDistance from the current vertex to the finish vertex.

gr = RandomGraph[{30, 40}];
ends = {1, 30};
sub = paths[gr, ends];
e = EdgeList[gr] /. {x_ \[UndirectedEdge] y_ /; 
 GraphDistance[gr, x, 30] < GraphDistance[gr, y, 30] :> y \[DirectedEdge] x, 
   x_ \[UndirectedEdge] y_ /; 
 GraphDistance[gr, y, 30] <= GraphDistance[gr, x, 30] :>  x \[DirectedEdge] y}
gr1 = Graph[e, ImagePadding -> 15];

HighlightGraph[gr1, {Graph[sub], Style[1, Green], Style[30, White]}, 
 VertexLabels ->  Table[i -> Style[GraphDistance[gr1, i, 30], 16], {i, 
    Union[Level[sub, {-1}]]}], 
    VertexSize -> {1 -> Large, 30 -> Large}, 
    GraphHighlightStyle -> "Thick", ImagePadding -> 15]

directed graph


Below is a variant that displays (a) the vertex indices (small font size) and the distance from the finish vertex on the EdgeLabel (large font).

HighlightGraph[gr1, {Graph[sub], Style[1, Green], Style[30, White]}, 
   VertexLabels -> (v = Union[Level[sub, {-1}]]) /. {i_Integer :> (i -> i)},
   EdgeLabels -> sub /. {x_ \[DirectedEdge] y_ :> (x \[DirectedEdge] y) -> 
   Style[ GraphDistance[gr, x, 30], 14, Background -> White]},
   VertexSize -> {1 -> Large, 30 -> Large}, 
   GraphHighlightStyle -> "Thick", ImagePadding -> 15, ImageSize -> 600]

directed graph 2

$\endgroup$
5
  • $\begingroup$ Any such crossing can be handled by recognizing that there are two or more ways to reach it, all have the same length, and so the problem can be split into subproblems. Specifically, we'll have the Cartesion product of min paths from start to crossing and min paths from crossing to finish. Also one must account for min paths that do not hit the crossing vertex. All that said, labeling by distance to finish seems like a useful thing to have. $\endgroup$ Apr 12, 2012 at 16:53
  • $\begingroup$ I'm wondering about "Any such crossing can be handled by recognizing that there are two or more ways to reach it, all have the same length". There may be only one way to reach the crossing (from a pre-selected start node); namely, if the in-degree is one. Note: I'm considering the union of shortest paths to be a directed sub-graph. By the way, is it possible for MMA to diagram a graph with a mix of directed and undirected edges. (I know multi graphs are not supported, but I would have thought that as long as there are no loops, and no more than a single edge between a pair of vertices...) $\endgroup$
    – DavidC
    Apr 12, 2012 at 17:34
  • $\begingroup$ Correct about in-degree of one. I should have been more explicit. I had in mind the case where you cannot get to the finish minimally by taking ANY of the edges leading out (that is, not the one you took in to the vertex). This was in accord with your concern that one might have to choose from amongst a proper subset, which does not happen when in-degree is one. $\endgroup$ Apr 12, 2012 at 18:23
  • $\begingroup$ This is nice, but it only works for graphs with unweighted edges, right? I wonder why this has been accepted seeing that the OP specifically asks for weighted edges. $\endgroup$ Aug 29, 2015 at 22:04
  • $\begingroup$ It should work with weighted edges. From the documentation on GraphDistance: "For a weighted graph, the distance is the minimum of the sum of weights along any path between s and t." $\endgroup$
    – DavidC
    Aug 30, 2015 at 12:47
16
$\begingroup$

To get the union of the shortest paths from i to j in graph gr you could do something like this

paths[gr_, {i_, j_}] := Module[{sub, dist, indices, dd, nbrs},
  dist = GraphDistance[gr, i, j];
  indices = {};
  dd = dist;
  Reap[Nest[
     Function[{vv},
      dd -= 1;
      nbrs = VertexList[NeighborhoodGraph[gr, #]] & /@ vv;
      nbrs = Pick[#, GraphDistance[gr, #, j] & /@ #, dd] & /@ nbrs;
      Sow /@ Flatten[Thread /@ Thread[vv \[UndirectedEdge] nbrs]];
      Union[Flatten[nbrs]]
      ], {i}, dist]][[2, 1]]]

This method works by selecting all neighbours of i whose distance to j is one less than the minimal distance from i to j. For each vertex in this list we then select the neighbours whose distance to j is two less than the minimal distance, etc. until we reach j.

Usage

gr = RandomGraph[{30, 50}];
ends = {1, 30};
sub = paths[gr, ends];
HighlightGraph[gr, {Graph[sub], Style[ends, Green]}]

Mathematica graphics

$\endgroup$
1
  • 1
    $\begingroup$ Nice work, but there is a directionality issue to be considered. First, the start vertex and and end vertex need to be distinguished. In addition, I believe the highlighted edges need to be directed edges. Otherwise, the "driver" in the middle of traffic cannot necessarily know which direction to take when arriving at a vertex with degree >1. (Some edges may lead back toward the start; others may lead towards the finish.) $\endgroup$
    – DavidC
    Apr 12, 2012 at 2:30
12
$\begingroup$
findMinPathsPoints[k_, ends_] := Module[{dist},
   dist = (GraphDistance[k, #[[1]]] + GraphDistance[k, #[[2]]]) &@ends;
   Complement[Flatten@Position[dist, Min[dist]], ends]];

(*Usage*)

n = 50;
points = {1, 10};
k = PetersenGraph[n, IntegerPart[n/4]]

Subgraph[k, Range@VertexCount@k, VertexStyle -> 
          Join[
              (# -> Red &)    /@ points, 
              (# -> Yellow &) /@ findMinPathsPoints[k, points]]]

enter image description here

$\endgroup$
9
$\begingroup$

With V10, you can use a combination of FindPath and GraphDistance. A (hopefully) self-explanatory example:

g = RandomGraph[{15, 44}, VertexLabels -> "Name"];
s = 1;
t = 2;
FindPath[g, s, t, {GraphDistance[g, s, t]}, All]
HighlightGraph[g, %]

In short, we find all paths between $s$ and $t$ of distance $d(s,t)$.

$\endgroup$
1
  • $\begingroup$ Yes this is very effective. $\endgroup$
    – apg
    Nov 8, 2019 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.