Shortest Paths: Dijkstra's Algorithm and Bellman-Ford Explained

In plain words — and an analogy

Think of a GPS routing app. You're at the airport and want to reach downtown. There are dozens of possible routes, each with a different travel time. The GPS doesn't try every route; it instead works outward from your current position, always extending the cheapest-so-far path. That is Dijkstra's algorithm: a disciplined greedy expansion that permanently settles the nearest unvisited destination first, then uses it to update estimates for its neighbors. A flight-cost analogy is even more direct — Dijkstra finds cheapest fares by always booking the next-cheapest leg first.

BFS found shortest paths when every edge counted as one step. But real graphs have *weights* — a road's length, a network link's latency, a flight's cost — and now 'shortest' means least total weight, not fewest edges. A three-edge route can beat a one-edge route if the single edge is expensive. This lesson covers the two classic weighted-shortest-path algorithms, each the right answer under different conditions.

The core operation: relaxation

Both algorithms share one primitive: edge relaxation. Keep a tentative shortest distance `dist[v]` for every vertex (all ∞ except the source at 0). Relaxing an edge (u → v) with weight w asks: *is the path to u, plus this edge, shorter than my current best to v?* If dist[u] + w < dist[v], update dist[v] = dist[u] + w and remember u as v's predecessor. Every shortest-path algorithm here is just a *strategy for the order in which to relax edges* until no relaxation can improve anything.

relax(u, v, w):
  if dist[u] + w < dist[v]:
    dist[v]   = dist[u] + w
    parent[v] = u

Dijkstra's algorithm: greedy with a priority queue

Dijkstra grows a shortest-path tree outward from the source, always finalizing the *closest not-yet-finalized* vertex next. That 'closest next' is exactly what a min-heap / priority queue delivers in O(log V).

Dijkstra(graph, source):
  dist   = {v: ∞ for all v};  dist[source] = 0
  parent = {v: None for all v}
  pq     = MinHeap()
  pq.push((0, source))         // (distance, vertex)

  while pq is not empty:
    d, u = pq.pop()
    if d > dist[u]: continue   // stale entry — skip
    for each edge (u→v, weight w):
      if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        parent[v] = u
        pq.push((dist[v], v))

  return dist, parent

Worked example: Dijkstra traced step by step

    4
A -----> B
|        |
|1      |1
v   2    v
C -----> D
 \
  \5
   v
    D (also reachable via C-D weight 5)

Edges: A→B(4), A→C(1), C→B(2), C→D(5), B→D(1)

Init:  dist = {A:0, B:∞, C:∞, D:∞}
       pq   = [(0,A)]

Step 1: pop (0,A) — finalize A
        relax A→B: dist[B] = 0+4 = 4  → push (4,B)
        relax A→C: dist[C] = 0+1 = 1  → push (1,C)
        dist = {A:0, B:4, C:1, D:∞}

Step 2: pop (1,C) — finalize C (smallest in heap)
        relax C→B: dist[B] = 1+2 = 3 < 4 → update! push (3,B)
        relax C→D: dist[D] = 1+5 = 6     → push (6,D)
        dist = {A:0, B:3, C:1, D:6}

Step 3: pop (3,B) — finalize B
        relax B→D: dist[D] = 3+1 = 4 < 6 → update! push (4,D)
        dist = {A:0, B:3, C:1, D:4}

Step 4: pop (4,B) — stale (dist[B]=3 < 4) → SKIP

Step 5: pop (4,D) — finalize D
        (no outgoing edges from D)

Step 6: pop (6,D) — stale (dist[D]=4 < 6) → SKIP

Final distances from A:
  A=0  C=1  B=3  D=4
Shortest path to D: A→C→B→D (cost 4), NOT A→B→D (cost 5)

Why greedy works here — and why negatives break it. When Dijkstra finalizes the closest frontier vertex, it assumes no cheaper path to that vertex could appear later. With non-negative weights that's guaranteed: any alternative route would have to pass through a vertex that's already farther away, and adding more (non-negative) edges can't get cheaper. A *negative* edge violates exactly this — a later, longer detour could suddenly drop below the finalized value — so Dijkstra can finalize a vertex too early and return a wrong answer. Non-negativity isn't a footnote; it's the load-bearing assumption.

Bellman-Ford: brute-force relaxation that handles negatives

Bellman-Ford makes no greedy assumption. It simply relaxes *every* edge, *V − 1 times over*. The insight: any shortest path has at most V − 1 edges (more would repeat a vertex, i.e., contain a cycle), and after the k-th full pass, all shortest paths using at most k edges are correct. So V − 1 passes settle every shortest path.

BellmanFord(graph, source):
  dist   = {v: ∞ for all v};  dist[source] = 0
  parent = {v: None for all v}

  for i in range(1, V):        // V-1 passes
    for each edge (u→v, weight w) in graph.edges:
      relax(u, v, w)           // update dist[v] if cheaper

  // Negative-cycle detection:
  for each edge (u→v, weight w) in graph.edges:
    if dist[u] + w < dist[v]:
      return "NEGATIVE CYCLE DETECTED"

  return dist, parent

Worked example: Bellman-Ford with a negative edge

Graph (directed):
  A→B (6), A→C (7), B→C (8), B→D (5), B→E (-4)
  C→B (-3), D→A (2), D→C (9), E→D 7

Source: A    V=5 vertices, so 4 passes needed

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

Pass 1 (relax all edges once):
  A→B: dist[B] = 6
  A→C: dist[C] = 7
  B→C: dist[C] = min(7, 6+8=14) = 7  (no change)
  B→D: dist[D] = 11
  B→E: dist[E] = 2      (6 + (-4) = 2)
  C→B: dist[B] = min(6, 7+(-3)=4) = 4  (improved!)
  E→D: dist[D] = min(11, 2+7=9) = 9
  ...
  After pass 1: {A:0, B:4, C:7, D:9, E:2}

Pass 2: dist[D] may improve via updated B...
  B→D: dist[D] = min(9, 4+5=9) = 9  (no change)
  ...further relaxations settle remaining paths

Pass 3, Pass 4: values stabilize (no more changes)

Detection pass (pass 5): no edge can be relaxed → no negative cycle

That final pass is a capability Dijkstra simply doesn't have: Bellman-Ford not only tolerates negative edges but *detects* negative cycles — invaluable for problems like currency-arbitrage detection (a cycle of exchange rates that multiplies to more than 1 is a negative cycle in log-space). The price is speed: V − 1 passes over E edges is O(V·E), considerably slower than Dijkstra on large graphs.

Dijkstra vs Bellman-Ford

Two honorable mentions the ecosystem completes the picture with: BFS is the special case for *unweighted* graphs (all weights 1 → Dijkstra degenerates to BFS, so don't build a heap you don't need), and the Floyd-Warshall algorithm computes shortest paths between *all pairs* of vertices in O(V³) using dynamic programming — the right tool when you need every-to-every distances on a smallish graph rather than single-source.

Common pitfalls

• Running Dijkstra on negative edges. The single most common shortest-path bug — it returns a plausible-looking wrong answer, not an error. Check for negative weights first; if present, use Bellman-Ford.
• Not skipping stale queue entries. Dijkstra pushes a vertex again each time its distance improves, leaving outdated entries in the heap. On pop, skip any vertex already finalized — otherwise you reprocess and may corrupt results.
• Forgetting Bellman-Ford's cycle check. Without the extra V-th pass you can't distinguish 'settled' from 'a negative cycle is driving values downward forever'.
• Using Dijkstra when BFS suffices. On an unweighted graph, plain BFS is simpler and just as correct — no heap overhead.
• Wrong number of Bellman-Ford passes. It's exactly V − 1 relaxation passes (plus one detection pass); fewer can leave long paths unsettled.

Practice problems

1. Network delay time. Given n nodes and directed weighted edges representing signal transmission times, find the time for a signal sent from a source node to reach all nodes, or report that not all nodes are reachable. (Classic Dijkstra.)
2. Cheapest flights within k stops. Find the cheapest flight from source to destination with at most k stops. (Modified Bellman-Ford — limit relaxation passes to k+1 instead of V−1.)
3. Currency arbitrage detection. Given a table of exchange rates between currencies, detect whether a sequence of exchanges starting and ending with the same currency can yield a profit. (Convert rates to negative logarithms; a negative cycle in that graph means arbitrage exists — Bellman-Ford detects it.)

Key takeaways

• Weighted shortest paths generalize BFS; both are built on edge relaxation.
• Dijkstra greedily finalizes the closest vertex using a min-priority queue — O((V+E) log V), but only correct with non-negative weights.
• Bellman-Ford relaxes all edges V−1 times — O(V·E), slower but handles negative edges and detects negative cycles.
• Choose by weights: non-negative and speed-critical → Dijkstra; negatives present or cycle detection needed → Bellman-Ford; unweighted → BFS; all-pairs → Floyd-Warshall.
• Non-negativity is the exact assumption that makes Dijkstra's greedy choice valid.

Shortest paths connect a source to everywhere. A related question flips the goal: connect *all* vertices as cheaply as possible — the minimum spanning tree, next, via Kruskal's and Prim's algorithms. Drill Dijkstra tracing in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play