Chapter 35: DSA Bellman-Ford Algorithm

DSA Bellman-Ford Algorithm – Let’s learn this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing the graph step by step, explaining every single decision slowly and clearly, showing exactly what happens in each iteration, and most importantly telling you why Bellman-Ford is needed, when you must choose it over Dijkstra, and how it detects negative cycles.

What is Bellman-Ford Algorithm?

Bellman-Ford is a single-source shortest path algorithm that works on graphs with any kind of edge weights — including negative weights — as long as there is no negative-weight cycle reachable from the source.

It was developed by Richard Bellman and Lester Ford (independently) in the 1950s.

Key points you must remember:

• Can handle negative edge weights (unlike Dijkstra)
• Can detect negative-weight cycles reachable from source
• Does not require priority queue / min-heap
• Slower than Dijkstra in most cases, but more general

Why do we need Bellman-Ford? (real motivation)

Dijkstra fails when there are negative weights.

Look at this example:

From A to D:

• Path A→B→? (no path to D)
• Path A→C→D = 2 + (-10) = -8

If we use Dijkstra:

• It will first pick C (dist=2)
• Then relax D → dist[D] = 2 + (-10) = -8
• But if there was a longer path that later gives even better distance (possible with negative edges), Dijkstra won’t reconsider nodes it already finalized

Bellman-Ford solves this by relaxing all edges multiple times — it gives every possible path a chance to improve the distance.

Core Idea of Bellman-Ford (very simple intuition)

Imagine you are trying to find the cheapest way to travel to every city from your home.

Bellman-Ford’s philosophy:

“If I relax all possible edges |V|-1 times, then I must have found the shortest path to every node — because the longest possible shortest path in a simple graph can have at most |V|-1 edges.”

After |V|-1 iterations:

• If any distance can still be improved → there is a negative cycle reachable from source

Bellman-Ford Algorithm Step-by-Step

1. Initialize distances:
   • dist[source] = 0
   • dist[every other node] = ∞
2. Relax all edges |V|-1 times:
   • For every edge (u → v) with weight w:
     • if dist[u] + w < dist[v]:
       • dist[v] = dist[u] + w
       • (optionally record previous node for path)
3. Check for negative cycle:
   • Do one more relaxation round
   • If any distance updates → negative cycle exists

Classic Example Graph (with negative weight)

Vertices: A, B, C, D, E

Edges:

• A → B : 6
• A → C : 7
• B → C : 5
• B → D : -4
• B → E : 8
• C → B : -2
• C → D : 9
• D → E : 2

Goal: Shortest path from A to all nodes

Initialize:

dist = {A:0, B:∞, C:∞, D:∞, E:∞}

Iteration 1 (relax all edges once):

• A→B: dist[B] = 0+6 = 6
• A→C: dist[C] = 0+7 = 7
• B→C: 6+5 = 11 > 7 → no
• B→D: 6+(-4) = 2 → dist[D] = 2
• B→E: 6+8 = 14 → dist[E] = 14
• C→B: 7+(-2) = 5 < 6 → update dist[B] = 5
• C→D: 7+9 = 16 > 2 → no
• D→E: 2+2 = 4 < 14 → update dist[E] = 4

Iteration 2:

• A→B: 0+6 = 6 > 5 → no
• A→C: 0+7 = 7 → no
• B→C: 5+5 = 10 > 7 → no
• B→D: 5+(-4) = 1 < 2 → update dist[D] = 1
• B→E: 5+8 = 13 > 4 → no
• C→B: 7+(-2) = 5 = 5 → no
• C→D: 7+9 = 16 > 1 → no
• D→E: 1+2 = 3 < 4 → update dist[E] = 3

Iteration 3:

• A→B: no
• A→C: no
• B→C: 5+5 = 10 > 7 → no
• B→D: 5+(-4) = 1 = 1 → no
• B→E: 5+8 = 13 > 3 → no
• C→B: no
• C→D: no
• D→E: 1+2 = 3 = 3 → no

No more updates → shortest paths found

Final distances from A:

• A: 0
• B: 5 (A→C→B)
• C: 7 (A→C)
• D: 1 (A→C→B→D)
• E: 3 (A→C→B→D→E)

Bellman-Ford Code (standard interview version)

Bellman-Ford vs Dijkstra – Very Important Interview Comparison

Rule of thumb (very common interview answer):

“I will use Dijkstra when all edge weights are non-negative because it is faster with priority queue. I will use Bellman-Ford when there can be negative weights or when I need to detect negative cycles.”

Summary – Bellman-Ford in one line each

• Single-source shortest path algorithm
• Works with negative edge weights (unlike Dijkstra)
• Time complexity: O(V × E) — slower but more general
• Detects negative cycles reachable from source
• Relaxes all edges |V|-1 times
• One of the top 5 most important graph algorithms for interviews
• Essential when negative weights are possible or cycle detection is required

Would you like to go deeper into Bellman-Ford or related topics?

Very natural next steps:

• Step-by-step dry run of Bellman-Ford with negative weights
• How Bellman-Ford detects negative cycle (visual proof)
• Bellman-Ford vs Dijkstra detailed comparison with same graph
• Negative cycle example – what happens and how to find the cycle
• Shortest path in graph with negative weights real use-cases

Just tell me which one you want next — I’ll explain it in the same detailed, step-by-step, human-teacher style with clear examples and visuals! 😊