Shortest Paths: Dijkstra, Bellman-Ford, and What "Negative Edges" Actually Break

Hook #

Course 3.1 lesson 4 ended with a promise: Dijkstra's algorithm is BFS with a priority queue, same invariant under weighted-cost ordering. This lesson is where that promise gets cashed in. Dijkstra's runs in O((V + E) log V) and finds the shortest weighted path from a source to every other vertex. But it only works when edge weights are nonnegative. When negative edges enter the picture, Dijkstra's silently produces wrong answers — and Bellman-Ford is what you reach for. The lesson is about the two algorithms and the boundary between them: what changes when negative edges show up, and why.

What you'll be able to do by the end of this lesson #

• Implement Dijkstra's algorithm using a priority queue, in O((V + E) log V).
• Implement Bellman-Ford for graphs with negative edges, in O(V × E).
• Detect a negative cycle in a weighted graph (Bellman-Ford catches it; Dijkstra silently produces wrong answers).
• Predict which algorithm to use given a graph's properties: nonnegative weights → Dijkstra; negative weights but no negative cycle → Bellman-Ford; need negative-cycle detection → Bellman-Ford.
• Articulate the edge relaxation technique that both algorithms share.

Why this matters here #

Shortest-path algorithms appear everywhere weighted graphs do: routing protocols (OSPF, BGP), GPS navigation, network latency optimisation, currency arbitrage detection (negative cycles in currency-exchange graphs), game pathfinding, and almost every production system with "find the cheapest way from A to B." Dijkstra is the one you'll write 95% of the time; Bellman-Ford is the niche but essential alternative when negative weights enter.

A second reason: Dijkstra is the clean example of greedy applied to graphs. The greedy choice — "always extract the closest unfinalised vertex" — is provably correct iff edge weights are nonnegative. Understanding why it fails for negative edges is the engineer's-lens that separates "I memorised Dijkstra" from "I know when to trust it."

We frame this lesson because MIT 6.006 and Abdul Bari cover the canonical content thoroughly. Our value-add is the boundary framing — what works, what breaks, why.

The engineer's lens #

Three things the canonical resources teach but don't put a name on:

1. Both algorithms share an edge relaxation primitive. Relaxation: "given current best known distance to vertex v, check if going through some other vertex u (via edge u→v) would be shorter. If yes, update."

textrelax(u, v, w):
  if dist[v] > dist[u] + w:
    dist[v] = dist[u] + w
    parent[v] = u

That's the only operation either algorithm performs. The order in which relaxations happen is what differs:

• Dijkstra: relax edges leaving the closest unfinalised vertex (priority-queue extract-min). Once a vertex is "finalised," never relax it again.
• Bellman-Ford: relax every edge in the graph, repeatedly. Do this V-1 times.

The shared shape: both are dynamic programming on the relaxation operator. Dijkstra is greedy DP — the order of relaxation matters; once a vertex's distance is finalised, it's frozen. Bellman-Ford is brute-force DP — relax everything until distances stop changing; the order doesn't matter (within a pass) because every edge gets considered every iteration.

2. Dijkstra requires nonnegative edges; here's why. Dijkstra's correctness proof uses a "greedy-stays-ahead" argument: when we extract a vertex v from the priority queue, no shorter path to v exists, because any such path would have to go through some vertex with distance less than v's — but every such vertex has already been finalised, and no edge from a finalised vertex can decrease another's distance (edge weights are nonnegative, so adding an edge can only increase distance).

The argument breaks when edge weights can be negative. A negative edge from a finalised vertex could decrease the distance to a previously-finalised vertex — but Dijkstra never revisits finalised vertices, so the update is missed.

Concrete counterexample:

text        2
   A ───────► B
   │          │
   │ 1        │ -3
   ▼          ▼
   C ────────► D
        1

Dijkstra from A: extract A (d=0), relax A→B (d=2), relax A→C (d=1). Extract C (d=1), relax C→D (d=2). Extract D (d=2). Extract B (d=2), relax B→D (d = 2 + (-3) = -1, which would be a shorter path to D!) — but D is already finalised. Final answer: d[D] = 2. Correct: d[D] = -1 (via B). Dijkstra silently produced the wrong answer.

The fix: use Bellman-Ford when negative edges are possible.

3. Bellman-Ford detects negative cycles "for free." A negative cycle means: there's a cycle in the graph whose total weight is negative. Walking that cycle decreases distance indefinitely; "shortest path" becomes undefined (negative infinity).

Bellman-Ford detects this with one extra pass: after V-1 iterations (which suffice for any acyclic shortest path), do one more pass. If any edge can still be relaxed, a negative cycle exists.

The technique: relax all edges V times. If the V-th pass changes any distance, the V-th relaxation could only have come from a cycle that decreases distance — a negative cycle.

This is why Bellman-Ford is the algorithm of choice for currency-arbitrage detection: build a graph where edge weights are -log(exchange rate); a negative cycle in this graph corresponds to a profitable cycle of trades. The algorithm finds them.

The three-algorithm comparison #

For sparse graphs with nonnegative weights, Dijkstra is unbeatable in practice. For dense graphs or graphs with negative weights, Bellman-Ford (or Floyd-Warshall for all-pairs). The choice is determined by the input.

What to focus on in the canonical resources #

• MIT 6.006 Lectures 13-15 — Dijkstra's correctness proof, Bellman-Ford analysis, Johnson's algorithm (combining the two for all-pairs). ~3 hours total.
• Abdul Bari's videos on Dijkstra and Bellman-Ford — ~60 minutes total. The traces are the load-bearing pedagogy.
• Visualgo SSSP — interactive. Try inserting a negative edge into Dijkstra; watch it produce a wrong answer.
• NeetCode Advanced Graphs — 10-15 problems. Practice converts theory to fluency.
• What to skip on first pass — Johnson's algorithm (combining Bellman-Ford reweighting with Dijkstra for all-pairs). It's clever but Floyd-Warshall (Lesson 2) is more commonly used. Cover when needed.
• What to come back to later — A* search (Dijkstra with a heuristic), bidirectional Dijkstra. Standard pathfinding improvements; covered in Course 11.x (AI) or Course 13.x (game pathfinding).

What to come back with #

Three predictions:

1. Run Dijkstra by hand on this graph from source A: 4 A ────► B │ │ 1│ │ 2 │ │ ▼ ▼ C ────► D 3 Trace the priority queue at each step. What's the final distance to D?

2. Find the bug. A teammate uses Dijkstra on a graph with edge weights [1, 2, -1, 3]. They get an answer they don't trust. Explain what's wrong and what they should use instead.

3. When does Bellman-Ford terminate after V-1 iterations vs. needing the V-th detection pass? Construct a tiny example of each.

Where this connects #

Backward: Course 3.1 lesson 4 (BFS in depth) introduced the layer invariant that Dijkstra generalises — when v is popped from the priority queue, every closer vertex has already been popped. The proof shape is the same; the priority queue replaces FIFO. Course 3.3 lesson 3 (greedy correctness) gives the proof technique — Dijkstra is the canonical greedy-stays-ahead application. Course 2.2 lesson 5 (heaps) provides the priority queue that makes Dijkstra O((V+E) log V).

Forward: Lesson 2 (Floyd-Warshall) generalises to all-pairs shortest paths via DP. Lesson 3 (MST) uses similar greedy reasoning for spanning trees. Lesson 4 (max-flow) is another optimisation on graphs but with a different (LP-dual) flavour. Course 7.x (Distributed Systems) returns to shortest paths for routing protocols (BGP, OSPF — variants of Bellman-Ford and Dijkstra adapted for distributed updates).

The zc-route-planner capstone for Course 3.1 (which you may have built) is exactly Dijkstra in production. The zc-network-flow-visualizer project for this course will use max-flow (Lesson 4). The graphs you've already touched throughout the path keep producing new questions; the algorithms keep multiplying.