0
$\begingroup$

This question already has an answer here:

The code for finding all shortest paths from start vertex s to end vertex t is provided in BreadthFirstScan. The relevant parts are under Applications, then Shortest Path Applications, and in that section: the second example (for unweighted graphs).

Is there online info where an adaptation is given for graphs with edge weights (positive weights)?

The code for unweighted case is copied below to find all shortest paths in an unweighted graph, using the example of a grid graph:

s = 1; t = 3*4; 
g = GridGraph[{3, 4}, VertexSize -> {s -> Medium, t -> Medium}]

discoverFun[u_, v_, d_] :=  If[u != v,  PropertyValue[{g, u},      
"ShortestPaths"] =  Table[Append[p, u], {p, PropertyValue[{g, v}, 
"ShortestPaths"]}];  PropertyValue[{g, u}, "Distance"] = d]

revisitFun[u_, v_] :=  If[PropertyValue[{g, u}, "Distance"] ==     
PropertyValue[{g, v}, "Distance"] + 1,  PropertyValue[{g, u}, 
"ShortestPaths"] =  Join[PropertyValue[{g, u}, "ShortestPaths"],     
Table[Append[p, u], {p, PropertyValue[{g, v}, "ShortestPaths"]}]]]

PropertyValue[{g, s}, "ShortestPaths"] = {{s}}; 
PropertyValue[{g, s}, "Distance"] = 0;

BreadthFirstScan[g,  s, {"DiscoverVertex" -> discoverFun, 
"VisitedVertex" -> revisitFun,  "UnvisitedVertex" -> revisitFun}];

Table[HighlightGraph[g, p], {p,  PathGraph /@ PropertyValue[{g, t}, 
"ShortestPaths"]}]
$\endgroup$

marked as duplicate by MarcoB, Henrik Schumacher, m_goldberg, bbgodfrey, glS Mar 4 at 11:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Have you seen this? Finding all shortest paths between two vertices. It uses GraphDistance which, as I understand it, should automatically work with weighted graphs. $\endgroup$ – MarcoB Feb 26 at 19:13
  • $\begingroup$ Thanks. It seems that GraphDistance may indeed do the trick. I will check it out. $\endgroup$ – Mike Feb 26 at 19:25