0
$\begingroup$

I am fairly new to Mathematica. I currently have a large weighted undirected graph representing a road network and I have a number of locations that I want to find the shortest paths between. There are currently two options with the FindShortestPath function; vertex a to b or vertex a to ALL.

Is there away to find the shortest path from a to a, c, d, e and f all in one instead of running the query each time for every shortest path.

I also am trying to find a way to table the GraphDistance for each shortest path.

I have a large graph with 1000s of vertices so scrolling through the GraphDistanceMatrix is a nightmare.

Cheers!

$\endgroup$
  • 3
    $\begingroup$ The docs mention the syntax needed to generate a ShortestPathFunction[] from your graph. Have you tried that already? $\endgroup$ – J. M. will be back soon Aug 3 '17 at 6:10
  • $\begingroup$ Hey @J.M. I have tired the spf but still can only input one at a time. I am not sure how to write it into a script so I can input a whole list of vertices at once. Maybe the better way to word the question is: Which vertex (from a specific list of vertices, not all in the graph) {b, c, d, e, f} is closer to vertex a ? $\endgroup$ – Emma Aug 3 '17 at 7:16
  • 1
    $\begingroup$ If spf = FindShortestPath[graph, All, All], then do spf[a, #] & /@ {b, c, d, e, f}... right? $\endgroup$ – J. M. will be back soon Aug 3 '17 at 7:39
  • $\begingroup$ I do not understand your question. You said yourself that it is possible to find shortest paths from a to All. Is this not what you want—find shortest paths from one vertex to all others? Note that finding it only to some (instead of all) others will not help with performance: the algorithm works in such a way that it discovers all shortest paths starting from one vertex. $\endgroup$ – Szabolcs Aug 3 '17 at 12:10
  • $\begingroup$ If you need only the distance (but not the exact path) from some vertices to some others (but not the full graph distance matrix), try IGDistanceMatrix form IGraph/M. In these cases it can significantly outperform GraphDistanceMatrix. $\endgroup$ – Szabolcs Aug 3 '17 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.