5
$\begingroup$

I want to do a shortest path algorithm. My direct and not acyclic graph contains only positive numbers. I have to do the scan for all pairs of nodes in complete depth in python. My graph is big (100x100x100 (with time-steps) and I have to do it in a time efficient way. I tried to do it with Dijkstra but it was far too slow. I also tried a Floyd-Warshall algorithm but I think that this algorithm doesn't scan the graph in complete depth (?). I would be thankful for other algorithms and additional advices.

$\endgroup$
10
  • 2
    $\begingroup$ You can refer to this post for an answer. $\endgroup$
    – Kuifje
    May 31 at 8:50
  • 2
    $\begingroup$ Are you looking for the shortest path between two specific nodes? or between one specific node and all other nodes? or between all pairs of nodes? $\endgroup$
    – fontanf
    May 31 at 11:23
  • 1
    $\begingroup$ Then, the most efficient is to run a Dijkstra algorithm for each node. If you really want the shortest paths between all pairs, there is not much more you can do. Your options are: 1) not computing the shortest paths between all pairs, for example, for each node, you only compute the shortest paths to the 100 closest nodes, 2) use a better implementation, in Cython or C++, you might already gain a factor 10, but it might not be sufficient $\endgroup$
    – fontanf
    Jun 1 at 6:33
  • 1
    $\begingroup$ If the graph is very dense (i.e. the number of edges is close to the number of vertices squared) Floyd-Warshall would be faster than Dijkstra. I don't understand what you mean by "scan the graph in complete depth"? $\endgroup$ Jun 3 at 18:27
  • 2
    $\begingroup$ Also, could you give a bit more information about the structure of your graph? Do you have some information related to the time-steps, for instance? For example, if you can assume that the distance between two nodes can never be more than their distance in time, more clever algorithms than Dijkstra or Floyd-Warshall could be possible. $\endgroup$ Jun 3 at 18:47
1
$\begingroup$

I think these are promising options:

  1. floyd-warshall algorithm for dense graphs
  2. johnson algorithm for sparse graphs
  3. (not sure if it's worth to try and it will work well) dijkstra algorithm parallelized for each vertex

Regarding your question, a correct floyd-warshall implementation scans all the pairs.

$\endgroup$

Your Answer

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

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