**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**.

- 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
**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) |

**Bellman-Ford Algorithm Iteration#1**

The values of nodes after the `1`

are ^{st} iteration**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) |

**Bellman-Ford Algorithm Iteration#2**

The values of nodes after the `2`

are ^{nd} iteration**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) |

**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.

## 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.