Bellman ford algorithm is a minimization algorithm used for encountering the shortest paths like Dijkstra’s Algorithm. It is also known as the single source shortest path but the main property which makes it different from Dijkstra’s algorithm is that it works for negative edge weights as well. Bellman-Ford is mostly used in distributed systems.
Implementation
Consider the following graph;
Explanation
- Step-01: Find the number of iterations to be performed.
- Total nodes are 6 (A, B, C, D, E, and F), and the number of iterations will be 1 less than the number of nodes which is 6 – 1 = 5.
- Step-02: Initialization
- Initialize the value of the source node with 0, and the rest of the nodes with infinity as shown below:
- Step-03: What to do in each iteration?
For each iteration, visit every edge of the graph and update values accordingly.
Now, for any edge from X to Y,
Value of node Y = Value of node X + Edge Weight
If this value of node Y is less than its previous value then UPDATE it. Else let the value remain unchanged. The value of a single node can be updated 2 or more times in the same iteration.
Iteration #1
| Nodes: | A | B | C | D | E | F | Node, Value |
| Current Values: | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | A, 0 |
| Edges(X-Y) | |||||||
1. A-B | 0 | 0+6= 6 | ∞ | ∞ | ∞ | ∞ | B, 6 (Updated) |
2. A-C | 0 | 6 | 0+4= 4 | ∞ | ∞ | ∞ | C, 4 (Updated) |
3. A-D | 0 | 6 | 4 | 0+5= 5 | ∞ | ∞ | D, 5 (Updated) |
4. B-E | 0 | 6 | 4 | 5 | 6+(-1)= 5 | ∞ | E, 5 (Updated) |
5. C-E | 0 | 6 | 4 | 5 | 4+3= 7 | ∞ | E, 5 (Remain Same) |
6. D-C | 0 | 6 | 5+(-2)= 3 | 5 | 5 | ∞ | C, 3 (Updated) |
7. D-F | 0 | 6 | 3 | 5 | 5 | 5+(-1)= 4 | F, 4 (Updated) |
8. E-F | 0 | 6 | 3 | 5 | 5 | 5+3= 8 | F, 4 (Remain Same) |
9. C-B | 0 | 3+(-2)= 1 | 3 | 5 | 5 | 4 | B, 1 (Updated) |
The values of nodes after the 1st iteration are A=0, B=1, C=3, D=5, E=5, and F=4. These values will be used as current values in the next iteration.
Iteration #2
| Nodes: | A | B | C | D | E | F | Node, Values |
| Current Values: | 0 | 1 | 3 | 5 | 5 | 4 | A, 0 |
| Edges(X-Y) | |||||||
| 1. A-B | 0 | 0+6= 6 | 3 | 5 | 5 | 4 | B, 1 (Remain same) |
| 2. A-C | 0 | 1 | 0+4= 4 | 5 | 5 | 4 | C, 3 (Remain same) |
| 3. A-D | 0 | 1 | 3 | 0+5= 5 | 5 | 4 | D, 5 (Remain same) |
| 4. B-E | 0 | 1 | 3 | 5 | 1+(-1)= 0 | 4 | E, 0 (Updated) |
| 5. C-E | 0 | 1 | 3 | 5 | 3+3= 6 | 4 | E, 0 (Remain Same) |
| 6. D-C | 0 | 1 | 5+(-2)= 3 | 5 | 0 | 4 | C, 3 (Remain Same) |
| 7. D-F | 0 | 1 | 3 | 5 | 0 | 5+(-1)= 4 | F, 4 (Remain Same) |
| 8. E-F | 0 | 1 | 3 | 5 | 0 | 0+3= 3 | F, 3 (Updated) |
| 9. C-B | 0 | 3+(-2)= 1 | 3 | 5 | 0 | 3 | B, 1 (Remain Same) |
The values of nodes after the 2nd iteration are A=0, B=1, C=3, D=5, E=0, and F=3. These values will be used as current values in the next iteration.
Iteration #3
| Nodes: | A | B | C | D | E | F | Node, Values |
| Current Values: | 0 | 1 | 3 | 5 | 0 | 3 | A, 0 |
| Edges(X-Y) | |||||||
| 1. A-B | 0 | 0+6= 6 | 3 | 5 | 0 | 3 | B, 1 (Remain same) |
| 2. A-C | 0 | 1 | 0+4= 4 | 5 | 0 | 3 | C, 3 (Remain same) |
| 3. A-D | 0 | 1 | 3 | 0+5=5 | 0 | 3 | D, 5 (Remain same) |
| 4. B-E | 0 | 1 | 3 | 5 | 1+(-1)=0 | 3 | E, 0 (Remain same) |
| 5. C-E | 0 | 1 | 3 | 5 | 3+3=6 | 3 | E, 0 (Remain Same) |
| 6. D-C | 0 | 1 | 5+(-2)=3 | 3 | 0 | 3 | C, 3 (Remain Same) |
| 7. D-F | 0 | 1 | 3 | 5 | 0 | 5+(-1)=4 | F, 4 (Remain Same) |
| 8. E-F | 0 | 1 | 3 | 5 | 0 | 0+3=3 | F, 3 (Remain same) |
| 9. C-B | 0 | 3+(-2)=1 | 3 | 5 | 0 | 3 | B, 1 (Remain same) |
Since there is no change or update in any value so there is no need to perform further iterations, this is a stopping condition. In case we don’t find this condition we will perform iterations till the number we found the Step-01 above, which was 5 in this case.
Results
The shortest distance of each node from the source node A is:
- A → A: 0
- A → B: 1
- A → C: 3
- A → D: 5
- A → E: 0
- A → F: 3
Properties of Bellman-Ford Algorithm
- Bellman-Ford algorithm uses the dynamic approach.
- It provides solutions for negative edge weights as well.
Drawbacks of the Bellman-Ford Algorithm
- Bellman-Ford provides solutions for negative edge weights with directed graphs only.
- It takes more time to find solutions than Dijkstra’s algorithm.
