CODEWITHSUNDEEP
shortest-pathfloyd-warshallbellman-ford
Noah Corlew
Noah Corlew

Reputation: 61

Would n calls of Bellman Ford be faster than Floyd-Warshall when finding the shortest distance from each node to each other node?

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?

Upvotes: 3

Views: 1103

Answers (1)

Nicholas Pipitone
Nicholas Pipitone

Reputation: 4192

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.

Upvotes: 2

Related Questions