What is the Bellman-Ford Algorithm?

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.


Consider the following graph;

Bellman Ford Algorithm
Bellman-Ford Algorithm Implementation


  • 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:
Bellman-Ford Algorithm implementation
Bellman-Ford Algorithm Implementation
  • 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:ABCDEFNode, Value
Current Values:0A, 0
1. A-B00+6= 6B, 6 (Updated)
2. A-C060+4= 4C, 4 (Updated)
3. A-D0640+5= 5D, 5 (Updated)
4. B-E06456+(-1)= 5E, 5 (Updated)
5. C-E06454+3= 7E, 5 (Remain Same)
6. D-C065+(-2)= 355C, 3 (Updated)
7. D-F063555+(-1)= 4F, 4 (Updated)
8. E-F063555+3= 8F, 4 (Remain Same)
9. C-B03+(-2)= 13554B, 1 (Updated)
Bellman-Ford Algorithm Iteration#1

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:ABCDEFNode, Values
Current Values:013554A, 0
1. A-B00+6= 63554B, 1 (Remain same)
2. A-C010+4= 4554C, 3 (Remain same)
3. A-D0130+5= 554D, 5 (Remain same)
4. B-E01351+(-1)= 04E, 0 (Updated)
5. C-E01353+3= 64E, 0 (Remain Same)
6. D-C015+(-2)= 3504C, 3 (Remain Same)
7. D-F013505+(-1)= 4F, 4 (Remain Same)
8. E-F013500+3= 3F, 3 (Updated)
9. C-B03+(-2)= 13503B, 1 (Remain Same)
Bellman-Ford Algorithm Iteration#2

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:ABCDEFNode, Values
Current Values:013503A, 0
1. A-B00+6= 63503B, 1 (Remain same)
2. A-C010+4= 4503C, 3 (Remain same)
3. A-D0130+5=503D, 5 (Remain same)
4. B-E01351+(-1)=03E, 0 (Remain same)
5. C-E01353+3=63E, 0 (Remain Same)
6. D-C015+(-2)=3303C, 3 (Remain Same)
7. D-F013505+(-1)=4F, 4 (Remain Same)
8. E-F013500+3=3F, 3 (Remain same)
9. C-B03+(-2)=13503B, 1 (Remain same)
Bellman-Ford Algorithm Iteration#3

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.


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.

Stay in the Loop

Get the daily email from Algoideas that makes reading the news actually enjoyable. Join our mailing list to stay in the loop to stay informed, for free.

Latest stories

- Advertisement -

You might also like...