Introduction

Bellman Ford Algorithm is a shortest path algorithm that works even when the graph contains negative edge weights.

You are given:

  • Weighted directed graph
  • Source node

Goal:

Find shortest distance from source to all vertices.

Unlike Dijkstra, Bellman Ford can handle negative weights.

Example

Input

Vertices = 5Edges:
0 → 1 (5)
0 → 2 (4)
1 → 3 (3)
2 → 1 (6)
3 → 2 (-2)

Output

Distance from source 0:

0 = 0
1 = 5
2 = 4
3 = 8
4 = INF

Key Observation

A shortest path can contain at most V-1 edges.

Therefore relaxing all edges V-1 times guarantees shortest distances.

Algorithm

  1. Initialize distances.
  2. Distance of source = 0.
  3. Relax all edges V-1 times.
  4. Update distances whenever shorter path is found.
  5. Perform one extra iteration.
  6. If distance still updates, negative cycle exists.

Dry Run

Initial

dist = [0, INF, INF, INF]

First Relaxation

0 → 1 = 5
dist[1] = 5

Next Relaxation

 1 → 3 = 3dist[3] = 8

Next Relaxation

 3 → 2 = -2dist[2] = 4

Final

[0,5,4,8]

Approach : Edge Relaxation

Repeatedly relax every edge.

If a shorter path exists, update the destination distance.

After V−1 iterations, all shortest paths become stable.

Practice

Complexity Analysis

Time Complexity: O(V × E)Explanation: All edges are relaxed V−1 times. Each iteration processes every edge once.

Space Complexity: O(V)
Explanation: A distance array of size V is used to store shortest distances from the source.

Why This Problem is Important

Bellman Ford is one of the few shortest path algorithms that works correctly with negative edge weights.

Common Beginner Mistakes

  • Forgetting V−1 relaxations.
  • Missing negative cycle detection step.
  • Using Bellman Ford when Dijkstra is sufficient.
  • Incorrect distance initialization.

Interview Tip

Always mention:

Bellman Ford can handle negative weights and can also detect negative weight cycles, unlike Dijkstra's Algorithm.

Related Questions

  • Floyd Warshall Algorithm
  • Dijkstra Algorithm
  • Network Delay Time
  • Cheapest Flights Within K Stops
  • Path With Maximum Probability

Final Takeaway

Bellman Ford is a powerful shortest path algorithm that uses edge relaxation and supports negative edge weights. Its ability to detect negative cycles makes it a very important graph algorithm.