Bellman-Ford Algorithm

The cover image was generated by ChatGPT.

Introduction

To address the limitation in Dijkstra’s Algorithm, which cannot handle paths with negative edge weights, the Bellman-Ford Algorithm was developed. The Bellman-Ford Algorithm performs $V - 1$ relaxation operations for $V$ nodes, repeatedly relaxing all edges to continuously improve and find the shortest paths.

Terminology

What is Relaxation?

Relaxation is the process of attempting to use an edge to update the currently known shortest distance to a node. If this edge provides a shorter path, the distance is updated.

What is a Negative Weight Cycle?

A negative weight cycle occurs when a set of nodes forms a cycle whose total edge weight is negative. During the Bellman-Ford Algorithm, such a cycle causes the algorithm to loop indefinitely, making the shortest distance shrink continuously, potentially toward negative infinity, resulting in the inability to define a shortest path.

Why $|V| - 1$ Relaxations?

$V$ represents the number of vertices in the graph. No matter which vertex you start from, the shortest path to any other vertex will pass through at most $|V| - 1$ edges ($E$). Therefore, if relaxation is still possible in the $|V|$-th iteration, it indicates a cycle, meaning a negative weight cycle exists.

How It Works

As shown in the figure above, suppose there are six locations labeled $A$, $B$, $C$, $D$, $E$, and $F$ in order. Taking point $A$ as the starting point and point $F$ as the destination, the goal is to find the path from $A$ to $F$. Each path has its own corresponding weight, which can be positive or negative. To simplify the problem, the directions of the paths are specified.

To find the path from point $A$ to point $F$, a table is created to record the previous location during the pathfinding process. All initial distances are set to $\infty$. Since there are 6 points in total, $|V| - 1 = 6 - 1 = 5$ relaxation rounds will be performed. In each round, every edge must be traversed to update the shortest distance to each node.

Since the starting point is $A$, the distance for point $A$ is set to 0 at the beginning of the calculation.

First Relaxation Round

Calculate the neighbors of $A$, which are $B$ and $C$. Since the edge weights are $\overline{AB} = 1$ and $\overline{AC} = 4$, the distances from the starting point are calculated as $0 + 1 = 1$ and $0 + 4 = 4$, respectively. Both are smaller than the current distances of $\infty$ in the table, so the distances for $B$ and $C$ are updated, and their previous location is marked as $A$.

Next, check the neighbors of $B$, which are $C$, $D$, and $E$, and calculate as follows:

• The current distance to $B$ plus the edge weight $\overline{BC}$ is $1 + (-2) = -1$, which is smaller than the current distance to $C$. Therefore, update the distance and previous location of $C$.
• The current distance to $B$ plus the edge weight $\overline{BD}$ is $1 + 6 = 7$, which is smaller than the current distance to $D$. Therefore, update the distance and previous location of $D$.
• The current distance to $B$ plus the edge weight $\overline{BE}$ is $1 + 5 = 6$, which is smaller than the current distance to $E$. Therefore, update the distance and previous location of $E$.

Next, update the neighbor of $C$, which is $E$, with the following calculation:

• The current distance to $C$ plus the edge weight $\overline{CE}$ is $-1 + (-8) = -9$, which is smaller than the current distance to $E$. Therefore, update the distance and previous location of $E$.

Next, update the neighbor of $D$, which is $F$, with the following calculation:

• The current distance to $D$ plus the edge weight $\overline{DF}$ is $7 + (-6) = 1$, which is smaller than the current distance to $F$. Therefore, update the distance and previous location of $F$.

Next, update the neighbors of $E$, which are $D$ and $F$, with the following calculations:

• The current distance to $E$ plus the edge weight $\overline{ED}$ is $-9 + 9 = 0$, which is smaller than the current distance to $D$. Therefore, update the distance and previous location of $D$.
• The current distance to $E$ plus the edge weight $\overline{EF}$ is $-9 + 3 = -6$, which is smaller than the current distance to $F$. Therefore, update the distance and previous location of $F$.

Point $F$ is the destination and has no subsequent points. Once all points have been traversed, this relaxation round ends, and the next round of relaxation can begin.

Second Relaxation Round

Next, the second relaxation round begins. Starting from point $A$, its neighbors are $B$ and $C$, and the current distance to $A$ is 0. Since $\overline{AB} = 1$, adding this to $A$’s distance gives $0 + 1 = 1$, which is not less than $B$’s current distance of $-4$, so no update is made. Similarly, no update is made for point $C$.

After determining that the neighbors $B$ and $C$ of point $A$ do not require updates, we proceed to calculate for the other points starting from point $B$. The neighbors of $B$ are $C$, $D$, and $E$, and the calculations are as follows:

• The current distance to $B$ plus $\overline{BC}$ is $1 + (-2) = -1$, which is not less than $C$’s current distance of -1, so no update is made for $C$.
• The current distance to $B$ plus $\overline{BD}$ is $1 + 6 = 7$, which is not less than $D$’s current distance of 0, so no update is made for $D$.
• The current distance to $B$ plus $\overline{BE}$ is $1 + 5 = 6$, which is not less than $E$’s current distance of -9, so no update is made for $E$.

Next, update the neighbor of point $C$, which is $E$. The current distance to $C$ is $-1$, and adding the edge weight $\overline{CE} = -8$ results in $-1 + (-8) = -9$. Since this is not less than $E$’s current distance of $-9$, no update is made for $E$.

Next, update the neighbor of point $D$, which is $F$. The current distance to $D$ is $0$, and adding the edge weight $\overline{DF} = -6$ results in $0 + (-6) = -6$. Since this is not less than $F$’s current distance of $-6$, no update is made for $F$.

Finally, update the neighbors of point $E$, which are $D$ and $F$, with the following calculations:

• The current distance to $E$ plus $\overline{ED}$ is $-9 + 9 = 0$, which is not less than $D$’s current distance of 0, so no update is made for $D$.
• The current distance to $E$ plus $\overline{EF}$ is $-9 + 3 = -6$, which is not less than $F$’s current distance of $-6$, so no update is made for $F$.

Third Relaxation Round

Since all distances remained unchanged during the second round, there is no need to perform the third, fourth, or fifth relaxation rounds.

If a graph still allows further relaxation in the $|V|$-th round after completing $|V| - 1$ rounds, it indicates the presence of a negative weight cycle. This leads to infinite relaxations and makes it impossible to correctly determine the shortest path. In such cases, the algorithm should be stopped, and the graph should be revised or a different algorithm should be used.

Paths

Based on the above computations, the paths from point $A$ to each point are as follows:

$A \to B$ $$ A \Rightarrow B, $$

$A \to C$ $$ A \Rightarrow B \Rightarrow C, $$

$A \to D$ $$ A \Rightarrow B \Rightarrow C \Rightarrow E \Rightarrow D, $$

$A \to E$ $$ A \Rightarrow B \Rightarrow C \Rightarrow E, $$

$A \to F$ $$ A \Rightarrow B \Rightarrow C \Rightarrow E \Rightarrow F, $$

Algorithm

Based on the example above, the steps of the Bellman-Ford Algorithm can be summarized as follows:

1. Initialize all distances, set the shortest distance for every node $u$ as $dist[u] = \infty$, and set the starting point’s distance to 0.
2. Start the $i$-th round of relaxation.
3. For each edge with weight $w$, if the updated shortest distance $dist[u] + w$ is less than the current $dist[v]$, then update it as $dist[v] = dist[u] + w$ and record the previous node with $pre[v] = u$.
4. Repeat step 3 until all edges have been relaxed for that round.
5. Repeat step 2 while $i \leq |V| - 1$.
6. Perform the $|V|$-th round of relaxation. If any edge still satisfies $dist[u] + w < dist[v]$, then a negative weight cycle exists in the graph, and the algorithm should terminate.
7. Output the shortest path results.

Conclusion

The Bellman-Ford Algorithm is a simple yet powerful shortest path algorithm that can handle negative edge weights that something Dijkstra’s algorithm cannot. It is especially useful when the number of edges is not too large or when negative weights need to be considered.

References

• 貝爾曼-福特演算法. (November 14, 2024). Wikipedia, The Free Encyclopedia. Retrieved July 17, 2025, from https://zh.wikipedia.org/zh-tw/贝尔曼-福特算法

• 波波微课. (April 1, 2025). Bellman-Ford最短路径算法 [Video]. YouTube. Retrieved July 18, 2025, from https://youtu.be/YklWOOAR6rs