Bellman-Ford algorithm

Prerequisites

• Dijkstra's algorithm and edge relaxation.
• Directed weighted graphs as an edge list.
• Cycles in a graph.

The analogy

How it works

Precondition: negative edge weights are allowed, but no negative cycle may be reachable from the start; the algorithm detects one if it exists.

Start with one round by hand

Edges in this order: (0→1, 4), (0→2, 5), (2→1, −3), (1→3, 2). Start: dist = [0, ∞, ∞, ∞]. Relax every edge in order. Predict, then open "Check".

Finish the picture: a negative cycle

Add the edge 1 → 2 with weight 1. Now 1 → 2 → 1 costs 1 − 3 = −2.

• Going round the cycle. Predict what happens to dist[1] each time you go round.
  Check

  It drops by 2 each lap: 2, 0, −2, … There is no shortest path; it goes to −∞.

• The extra round. Predict the output of the check after $V - 1$ rounds.
  Check

  Some edge (for example 2 → 1) can still be relaxed, so the algorithm reports a negative cycle.

The rule in plain words

Set dist[source] = 0, others ∞. Do $V - 1$ rounds; in each round, relax every edge $u \to v$: if dist[u] + w < dist[v], update dist[v].

Then do one more pass. If anything still improves, report a negative cycle.

The code

Read this code after you have done a round by hand. It will make more sense.

int bellman_ford(int n, int m, int eu[], int ev[], int ew[], int s, int dist[]) {
    for (int i = 0; i < n; i++) dist[i] = INT_MAX;
    dist[s] = 0;
    for (int round = 1; round < n; round++)               /* n - 1 rounds */
        for (int j = 0; j < m; j++)                        /* relax every edge */
            if (dist[eu[j]] != INT_MAX && dist[eu[j]] + ew[j] < dist[ev[j]])
                dist[ev[j]] = dist[eu[j]] + ew[j];
    for (int j = 0; j < m; j++)                            /* one more round */
        if (dist[eu[j]] != INT_MAX && dist[eu[j]] + ew[j] < dist[ev[j]])
            return 0;                                      /* still improving: negative cycle */
    return 1;                                              /* distances are final */
}

flowchart TD
  A["dist[s] = 0, others infinity"] --> B["relax every edge"]
  B --> C{"done V - 1 rounds?"}
  C -->|no| B
  C -->|yes| D{"can any edge still be relaxed?"}
  D -->|yes| E["report a negative cycle"]
  D -->|no| F["distances are shortest paths"]
          

How fast is it?

There are $V - 1$ rounds, and each round relaxes all $E$ edges:

That's slower than Dijkstra's $O((V + E) \log V)$, the price of allowing negative edges. You can stop early if a round changes nothing.

Common mistakes

• Running only one round and assuming it is enough (it was here only because the edge order was lucky).
• Adding to ∞ (INT_MAX + w) for unreachable vertices, which overflows in C.
• Forgetting the negative-cycle check and reporting meaningless distances.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• It allows negative edges because no distance is declared final before all rounds are done.
• $V - 1$ rounds suffice because a shortest simple path has at most $V - 1$ edges.
• An improvement in round $V$ proves a negative cycle because without one, nothing can improve any more.
• It costs $O(VE)$ because every round relaxes every edge.
• Unreachable vertices are skipped because adding to ∞ is meaningless and overflows.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is Bellman-Ford like a rumour about cheap bus fares?
   Sample answer

   Each round, everyone tells their neighbours "you can reach this place through me for this price". After enough rounds, everyone knows their cheapest fare.

2. Walk through round 1 on the edges (0→1, 4), (0→2, 5), (2→1, −3), (1→3, 2).
   Sample answer

   dist[1] = 4, dist[2] = 5, then 2→1 lowers dist[1] to 2, then dist[3] = 4. Final: [0, 2, 5, 4].

3. Why does the code check dist[eu[j]] != INT_MAX before relaxing?

   A good answer mentions overflow.

   Sample answer

   An unreachable vertex has distance ∞; adding a weight to INT_MAX overflows in C, and a path from an unreachable vertex is meaningless anyway.

4. So what is Bellman-Ford, in one sentence?
   Sample answer

   A shortest-path algorithm that relaxes every edge $V - 1$ times, handling negative edges and detecting negative cycles.

5. Why are $V - 1$ rounds always enough without a negative cycle?

   A good answer counts edges on a shortest path.

   Sample answer

   A shortest path never repeats a vertex, so it has at most $V - 1$ edges, and round $k$ fixes every shortest path that uses $k$ edges.

6. What do Bellman-Ford and its negative-cycle check cost?
   Sample answer

   $O(VE)$ for the rounds plus $O(E)$ for the check; $O(V)$ extra space.

7. When would you choose Bellman-Ford over Dijkstra?
   Sample answer

   When the graph has negative edges, or when you need to detect negative cycles, such as arbitrage. Otherwise Dijkstra is faster.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the edge-order subtleties and the arbitrage example. I'd keep the gossip analogy, the round on the 4-vertex example, and "relax all edges $V - 1$ times, $O(VE)$, negative edges OK, detects negative cycles".

External resources

• VisuAlgo: Single-source shortest paths: choose Bellman-Ford and step through the rounds.
• GeeksforGeeks: Bellman-Ford: code with negative-cycle detection.
• Wikipedia: Bellman-Ford algorithm: proof and applications.

Videos

• YouTube search: Bellman-Ford explained: pick a walkthrough of the rounds.