3 ms·
Just a note, unless you have negative edges, running V Dijkstra's is likely to perform better than Floyd Warshall. Dijkstra's gives you distance from a single n
by chillee 8y ago
Just a note, unless you have negative edges, running V Dijkstra's is likely to perform better than Floyd Warshall. Dijkstra's gives you distance from a single node to all other nodes in V log E time. If you run it V times, you'll get V^2 log E, a substantial improvement upon V^3.
It also seems to me like it's likely to be easier parallelized, considering that the V runs of Dijkstra are completely independent.
- brianpgordon 8y agoHmm, wouldn't Dijkstra's be V E + V^2 log V? I take your point though. I suspect that I was dazzled by the cache locality advantages of dynamic programming and skeptical that messing about with a bunch of heap nodes would be faster, but looking at it now I bet you're right that knocking one of those Vs down to a log V would help. Thanks for the feedback!