# 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 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 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 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 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 at 18:47