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.
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.