2

Assuming that there are no negative edges.

Floyd-Warshall has a constant runtime of O(V^3). Bellman Ford has a worst case runtime of O(VE), but a best case of O(E).

So running BF for each individual node would have a worst case runtime of O(EV^2) but a best case of O(VE), is this correct?

Noah Corlew
  • 51
  • 4

1 Answers1

1

Bellman Ford will be slower than Floyd-Warshall in almost all cases. If the graph is a tree, then E = V, and both will be the same V^3. However, its very easy for E to be much larger. E can be up to V^2 in the case of a complete graph, where BF on just one node will take just as long as FW on the entire graph.

There's rarely a reason to use BF when Dijkstra's can solve the same problem in E+VlogV, which will be faster than VE in again all cases other than a simple tree.

Nicholas Pipitone
  • 4,002
  • 4
  • 24
  • 39
  • So could the same thing be said about n calls of Dijkstra's? – Noah Corlew Aug 02 '18 at 19:02
  • 2
    Running Dijkstra's for each node will be faster Floyd-Warshall in all cases other than when the graph is close to complete (Specifically, when `E` is appx equal to `V^2`). There's a reason why Dijkstra's algorithm is the famous one. The only time using Dijkstra's isn't the best is when you need negative edges (Where it ends up not working at all). – Nicholas Pipitone Aug 02 '18 at 19:17
  • @NicholasPipitone thank you for saying this! i've been scratching my head trying to make sense of this whole post: https://stackoverflow.com/questions/4212431/dijkstra-vs-floyd-warshall-finding-optimal-route-on-all-node-pairs. to state my reasoning for posterity - if dijkstra's - naively implemented, using an unordered array to keep track of distances takes o(n^2) - performing this once for each node as source (n times)... is... o(n^3). – TolkienWASP May 14 '20 at 05:22