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.
$\begingroup$
$\endgroup$
10
-
2$\begingroup$ You can refer to this post for an answer. $\endgroup$– KuifjeCommented May 31, 2021 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$– fontanfCommented May 31, 2021 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$– fontanfCommented Jun 1, 2021 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$– Paul BoumanCommented Jun 3, 2021 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$– Paul BoumanCommented Jun 3, 2021 at 18:47
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
I think these are promising options:
- floyd-warshall algorithm for dense graphs
- johnson algorithm for sparse graphs
- (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.
