# Quickest shortest path algorithm

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.

• You can refer to this post for an answer. May 31, 2021 at 8:50
• 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? May 31, 2021 at 11:23
• 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 Jun 1, 2021 at 6:33
• 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"? Jun 3, 2021 at 18:27
• 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. Jun 3, 2021 at 18:47