Mastering Graph Algorithms/

...

/

The Bellman-Ford Algorithm

The Bellman-Ford Algorithm

Learn how the Bellman-Ford algorithm works.

We'll cover the following...

The Bellman-Ford algorithm is a single-source shortest-paths algorithm discovered a few years before Dijkstra’s algorithm. Despite being slower than Dijkstra’s algorithm, it does have the following added advantages over it:

  • It works correctly in the presence of negative-weight edges and computes the shortest paths as long as they are well-defined.welldefined

  • If there’s a negative-weight cycle in the digraph that can be reached from the source vertex, Bellman-Ford has a way to detect this and alert the end user to the fact that the shortest-paths problem is not well-defined for the input digraph.

It’s interesting to know that the algorithm was discovered by Alfonso Shimbel in 1955 but is actually named after Richard Bellman and Lester Ford Jr., who also discovered the algorithm independently in 1958 and 1956, respectively.

Press + to interact

Core idea

The Bellman-Ford algorithm is a natural extension of the idea of path-relaxation and is simple to understand. The core idea behind the algorithm is to simply relax all edges of the digraph—again and again—for a total number of n−1n-1 rounds, where nn is the number of vertices. The algorithm comes with a guarantee that after n−1n-1 rounds, shortest paths from the source vertex are computed correctly (if they’re well-defined.)

Press + to interact

Visualization

In general, the order in which all the edges are relaxed in each round is not important. The algorithm works correctly regardless of how the edges are picked. However, the attribute values at the intermediate steps may differ depending on the order in which we relax the edges. So, to visualize how the algorithm works, we assume that the edges in the following example are relaxedRelaxation in the order shown:

Press + to interact
Initialization of the vertex attributes (dist and parent) where s is the source vertex. To avoid clutter, we use a dash to represent a nil value for the parent pointers. The order in which the edges are relaxed in each round is shown on the right.
1 / 26
Initialization of the vertex attributes (dist and parent) where s is the source vertex. To avoid clutter, we use a dash to represent a nil value for the parent pointers. The order in which the edges are relaxed in each round is shown on the right.

The algorithm

The Bellman-Ford algorithm performs n−1n-1 rounds of edge-relaxations, after which the expectation is that shortest paths from the source to all vertices are correctly computed, and no further edge-relaxations should reduce the values stored in the distdist ...