1. What Is the Bellman-Ford Algorithm?

The Bellman-Ford algorithm finds the shortest path from one starting vertex to every other vertex in a weighted graph. It was developed by Richard Bellman and Lester Ford Jr. in the late 1950s.

Its superpower: it works even when some edges have negative weights. Dijkstra's algorithm — the more famous shortest-path algorithm — breaks on negative weights. Bellman-Ford doesn't.

As a bonus, Bellman-Ford can also tell you if a graph has a negative-weight cycle (a loop where going around the cycle keeps reducing the total cost — meaning no true shortest path exists).

2. A Real-World Analogy

Imagine you're planning the cheapest flight route from Delhi to several cities. Most routes have positive costs (you pay). But some airlines offer cashback deals — flying a particular route gives you money back (negative weight). Bellman-Ford correctly handles this and finds the cheapest total route even with cashback deals factored in.

Dijkstra would incorrectly ignore the cashback routes because it assumes costs only go up. Bellman-Ford doesn't make that assumption — it checks every possible route multiple times to be sure.

3. How It Works — The Core Idea

Bellman-Ford uses a simple technique called edge relaxation. Relaxing an edge means checking: "Is there a shorter way to reach vertex v by going through vertex u first?"

Bellman-Ford repeats this relaxation for every edge in the graph, and does this V−1 times (where V = number of vertices). Why V−1? Because the longest possible shortest path in a graph with V vertices uses at most V−1 edges. After V−1 rounds, all shortest paths are guaranteed to be found.

4. Pseudocode

BELLMAN-FORD(Graph G, source s):
  // Step 1: Initialize distances
  for each vertex v in G:
    d[v] = ∞
  d[s] = 0

  // Step 2: Relax all edges V−1 times
  repeat (V − 1) times:
    for each edge (u, v, weight) in G:
      if d[u] + weight < d[v]:
        d[v] = d[u] + weight

  // Step 3: Check for negative-weight cycles
  for each edge (u, v, weight) in G:
    if d[u] + weight < d[v]:
      print "Negative cycle detected!"
      return

  return d

That's the entire algorithm — 3 clean steps. The simplicity is part of why it's so widely taught and used.

5. Step-by-Step Trace on a Graph

Let's trace Bellman-Ford manually on a small graph so you can see exactly what happens each round.

Vertices: A, B, C, D
Source: A

Edges (with weights):
  A → B : 4
  A → C : 2
  B → D : 3
  C → B : −3    ← negative weight!
  C → D : 5

Initialization: d[A]=0, d[B]=∞, d[C]=∞, d[D]=∞

Round 1 (relax all edges once)

After Round 1: d[A]=0, d[B]=−1, d[C]=2, d[D]=7

Round 2 (relax all edges again)

After Round 2: d[A]=0, d[B]=−1, d[C]=2, d[D]=2

Round 3 (V−1 = 3 rounds total)

No edges can be relaxed further. Distances are stable.

Notice how the negative edge C→B (weight −3) dramatically changed the results. Dijkstra would have missed this because it would have finalized d[B]=4 in the first step and never gone back.

6. Detecting Negative Cycles

A negative-weight cycle is a loop in the graph where the total weight around the loop is less than zero. If such a cycle exists, shortest paths are undefined — you could keep going around the cycle and decrease the "shortest path" forever.

Bellman-Ford detects this with a simple trick: after V−1 rounds, do one more relaxation pass. If any distance still decreases, a negative cycle must exist (because all legitimate shortest paths would already be stable after V−1 rounds).

Example — Negative Cycle:
A → B (1)
B → C (−4)
C → A (2)

Cycle weight: 1 + (−4) + 2 = −1  ← negative! Shortest path is undefined.

After V−1 rounds, if you relax A→B and find d[A] + 1 < d[B],
the cycle is detected.

Practical use: Currency arbitrage detection (finding profitable cycles in exchange rate graphs), financial risk systems, and network routing (detecting routing loops with shrinking costs).

7. Python Implementation

def bellman_ford(vertices, edges, source):
    """
    vertices: list of vertex names, e.g. ['A','B','C','D']
    edges: list of (u, v, weight) tuples
    source: starting vertex
    returns: dist dict, or None if negative cycle found
    """
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0

    # Relax all edges V-1 times
    for _ in range(len(vertices) - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Check for negative-weight cycles
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            print("Negative cycle detected — no valid shortest paths.")
            return None

    return dist

# Example usage
vertices = ['A', 'B', 'C', 'D']
edges = [
    ('A', 'B',  4),
    ('A', 'C',  2),
    ('B', 'D',  3),
    ('C', 'B', -3),
    ('C', 'D',  5),
]
result = bellman_ford(vertices, edges, 'A')
print(result)
# {'A': 0, 'B': -1, 'C': 2, 'D': 2}

8. Time and Space Complexity

For a dense graph (E ≈ V²), this becomes O(V³) — quite slow. For sparse graphs (E ≈ V), it's O(V²). This is why Bellman-Ford is used only when negative weights are present; for non-negative weights, Dijkstra is always faster.

9. Bellman-Ford vs Dijkstra — When to Use Which

Simple rule: Start with Dijkstra. Only switch to Bellman-Ford if your graph has negative edge weights.

10. Worked Examples

Example 1 — All Positive Weights (Verify Bellman-Ford Matches Dijkstra)

Graph: A→B(1), A→C(4), B→C(2), B→D(6), C→D(3)
Source: A

Round 1: d[B]=1, d[C]=4 (via A→C) or 3 (via A→B→C)→3 after C→B relaxed, d[D]=∞
Round 2: d[C] = min(4, 1+2) = 3, d[D] = min(∞, 1+6)=7, then d[D]=min(7, 3+3)=6
Round 3: No updates.
Round 4: No updates.

Result: A=0, B=1, C=3, D=6 ✓ (same as Dijkstra)

Example 2 — Negative Cycle Detection

Graph: A→B(1), B→C(2), C→B(−4)
Source: A

After 2 rounds (V−1=2): d[A]=0, d[B]=1, d[C]=3
Extra check round: C→B: d[C]+(−4) = 3−4 = −1 < d[B]=1 → UPDATE!
A distance still changed after V−1 rounds → Negative cycle: B→C→B detected!

11. Five Common Mistakes

Mistake 1 — Running only V−2 rounds instead of V−1

The algorithm needs exactly V−1 rounds to guarantee all shortest paths are found. The shortest path in a graph with V vertices has at most V−1 edges — one fewer round can miss the longest valid shortest path.

Mistake 2 — Using Bellman-Ford on undirected graphs with negative edges

An undirected negative edge is treated as two directed edges (u→v and v→u), both with negative weight. This automatically creates a negative cycle between u and v, so Bellman-Ford will always detect a "negative cycle" on undirected graphs with any negative edge. For undirected graphs, negative edges make the problem fundamentally unsolvable.

Mistake 3 — Not initializing distances to infinity

Every vertex except the source must start at infinity. If you initialize to 0, every relaxation check becomes meaningless because 0 + w is rarely less than 0 for positive w. The algorithm silently produces wrong results.

Mistake 4 — Skipping the negative cycle check

Many students implement V−1 rounds and return the dist array without the extra verification round. If a negative cycle exists, the returned distances are meaningless. Always add the cycle check round.

Mistake 5 — Thinking Bellman-Ford finds the path, not just the distance

The basic implementation only fills the dist[] array (distances). To reconstruct the actual path, you need a prev[] array that records which vertex updated each distance. Update it inside the relaxation step: if d[u]+w < d[v]: d[v]=...; prev[v]=u.

12. Frequently Asked Questions

13. Next Steps