Bellman-Ford Algorithm

Click to play video

The Bellman-Ford algorithm computes shortest paths from a single node to all other nodes in a weighted graph. You may be thinking,

Why can't I just use Dijkstra's algorithm for that?

You usually can, and you should because it's faster. The problem is that Dijkstra's algorithm can't handle negative weights in the graph. If there are negative weights, you'll need to use something different like Bellman-Ford.

The Bellman-Ford algorithm consists of two phases:

1. Relaxation Phase: This phase consists of n-1 iterations, where n is the number of nodes in the graph. During each iteration the edges are "relaxed," meaning the shortest path estimate for each edge is updated. If there are no negative cycles, the distance from the source to all nodes is guaranteed to be correct by the end of this phase.

2. Negative Cycle Detection Phase: A final iteration of edge relaxation is done, to check whether any distances are reduced further. If any distance can still be reduced, there must be a negative-weight cycle in the graph.

To summarize: not only does the Bellman-Ford algorithm handle negative weights, but it properly detects negative cycles.