Dijkstra's Algorithm

The Core Idea

Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It works by greedily settling vertices — always processing the closest unvisited vertex next.

GREEDY INVARIANT:
  When vertex u is extracted from the min-heap with distance d,
  dist[u] = d is the TRUE shortest distance from source to u.
  u is permanently settled — never updated again.

WHY THE INVARIANT HOLDS (non-negative edges only):
  Any alternative path to u must go through some other unvisited vertex v.
  All unvisited vertices have dist[v] >= dist[u] (heap extracts minimum).
  Any path through v has total length >= dist[v] + 0 >= dist[u].
  So no alternative path can be shorter. QED.

  With NEGATIVE edges: dist[v] + negative_edge < dist[u] is possible.
  Invariant breaks → algorithm produces wrong answers.

Algorithm Steps

INPUT:
  Weighted directed graph (non-negative weights).
  Source vertex s.

INITIALISE:
  dist[s] = 0, dist[all others] = ∞
  min-heap = {(0, s)}
  parent[] = {-1} for all vertices (for path reconstruction)

LOOP:
  While heap is not empty:
    (d, u) = extract-min from heap
    If d > dist[u]: skip (stale entry — shorter path already found)
    For each edge (u, v, weight):
      If dist[u] + weight < dist[v]:
        dist[v] = dist[u] + weight
        parent[v] = u
        push (dist[v], v) to heap   ← lazy: don't remove old entry

OUTPUT:
  dist[] = shortest distances from source to all vertices
  parent[] = predecessor on shortest path (for reconstruction)

Step-by-Step Trace

Graph (directed, weighted):

     0 ──4── 1
     │       │ \
     1       2   5
     │       │    \
     2 ──2── 1     3 ──3── 4

Adjacency list:
  0 → [(1,4), (2,1)]
  1 → [(3,1)]
  2 → [(1,2), (3,5)]
  3 → [(4,3)]
  4 → []

Dijkstra from source=0:

INIT: dist=[0,∞,∞,∞,∞], heap=[(0,0)], parent=[-1,-1,-1,-1,-1]

━━━ Extract (0, 0): u=0, d=0 ━━━
  0 ≤ dist[0]=0 → process (not stale)
  Edge 0→1 w=4: 0+4=4 < ∞ → dist[1]=4, parent[1]=0, push(4,1)
  Edge 0→2 w=1: 0+1=1 < ∞ → dist[2]=1, parent[2]=0, push(1,2)
  dist=[0,4,1,∞,∞]  heap=[(1,2),(4,1)]

━━━ Extract (1, 2): u=2, d=1 ━━━
  1 ≤ dist[2]=1 → process
  Edge 2→1 w=2: 1+2=3 < 4 → dist[1]=3, parent[1]=2, push(3,1)  ← UPDATE!
  Edge 2→3 w=5: 1+5=6 < ∞ → dist[3]=6, parent[3]=2, push(6,3)
  dist=[0,3,1,6,∞]  heap=[(3,1),(4,1),(6,3)]

━━━ Extract (3, 1): u=1, d=3 ━━━
  3 ≤ dist[1]=3 → process
  Edge 1→3 w=1: 3+1=4 < 6 → dist[3]=4, parent[3]=1, push(4,3)  ← UPDATE!
  dist=[0,3,1,4,∞]  heap=[(4,1),(4,3),(6,3)]

━━━ Extract (4, 1): u=1, d=4 ━━━
  4 > dist[1]=3 → STALE, skip

━━━ Extract (4, 3): u=3, d=4 ━━━
  4 ≤ dist[3]=4 → process
  Edge 3→4 w=3: 4+3=7 < ∞ → dist[4]=7, parent[4]=3, push(7,4)
  dist=[0,3,1,4,7]  heap=[(6,3),(7,4)]

━━━ Extract (6, 3): u=3, d=6 ━━━
  6 > dist[3]=4 → STALE, skip

━━━ Extract (7, 4): u=4, d=7 ━━━
  7 ≤ dist[4]=7 → process, no outgoing edges
  heap=[]

FINAL: dist=[0,3,1,4,7]
Path to 4: backtrack parent[] → 4←3←1←2←0 → reverse → [0,2,1,3,4]

Complete Implementation

Output:
Distances:      [0, 3, 1, 4, 7]
Path 0→4:       [0, 2, 1, 3, 4]
Unreachable:    []

Application 1: Network Delay Time

Problem: Given n nodes and travel times as directed edges [u, v, w], find the minimum time for all nodes to receive a signal sent from node k. Return -1 if not all reachable.

MODEL:
  Run Dijkstra from k.
  All nodes receive signal at time dist[i].
  "All nodes received" = max of all dist[i].
  If any dist[i] = ∞: some node unreachable → return -1.

Example: n=4, edges=[[2,1,1],[2,3,1],[3,4,1]], k=2
  Dijkstra from 2:
    dist[2]=0, dist[1]=1 (2→1:1), dist[3]=1 (2→3:1), dist[4]=2 (2→3→4:1+1=2)
  max(dist) = 2 → signal reaches all nodes in time 2.

Output:
2
3
-1

Application 2: Cheapest Flights Within K Stops

Problem: Find cheapest flight from src to dst with at most k stops (k+1 flights). Standard Dijkstra needs modification — limit path length.

MODIFICATION:
  State: (cost, node, stops_remaining)
  Start: (0, src, k) — at source with k stops left
  Relax: for each neighbour v with weight w:
    if stops > 0: push (cost+w, v, stops-1)
  Extract: minimum cost state where we reach dst

  DON'T use simple visited[] — same node can be reached with different stops remaining.

Example: n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1
  (0, 0, 1) → explore 0
    0→1:100 → (100, 1, 0)
    0→2:500 → (500, 2, 0)    ← direct flight
  (100, 1, 0) → explore 1, stops=0 means 0 more stops allowed
    1→2:100 → but stops=0 means this would be k+1=2 stops? NO:
    stops_remaining means stops (layovers) still usable.
    Going from 1→2 with stops=0 means: we've already made 1 stop (at 1),
    this flight arrives at dst. k=1 stop means 1 layover → 2 total flights. ✓
    (100+100, 2, -1)... actually: push if stops > 0 BEFORE arrival.

  Answer: 200 (via 0→1→2)

Output:
200  (0→1→2 with 1 stop = 2 flights)
500  (direct flight 0→2, 0 stops)
-1   (unreachable)

Dijkstra Variants Summary

STANDARD DIJKSTRA:
  State: (distance, vertex)
  Visit: skip if d > dist[u]
  Update: dist[v] = dist[u] + weight
  Use: single-source shortest path, positive weights

DIJKSTRA + PATH RECONSTRUCTION:
  Add parent[] array
  parent[v] = u when dist[v] is updated
  Backtrack target → source via parent[], reverse

DIJKSTRA WITH ARRAY (no heap):
  O(V²) — better for dense graphs
  Scan all unvisited vertices to find minimum each time
  No heap operations needed

MODIFIED DIJKSTRA (k stops / k hops limit):
  State: (cost, vertex, remaining_steps)
  Don't use settled[] — same vertex can be in multiple states
  Useful when path length is also constrained

BIDIRECTIONAL DIJKSTRA:
  Run Dijkstra from source AND target simultaneously
  Stop when searches meet
  ~2× faster in practice

MULTI-SOURCE DIJKSTRA:
  Push all sources at distance 0 into the heap initially
  Equivalent to single source with a virtual super-source

Complexity Summary

Common Mistakes

Not skipping stale heap entries. When a shorter path to vertex v is found, a new (dist[v], v) is pushed but the old entry remains. When the old entry is extracted, d > dist[v] — skip it. Without this check, you reprocess vertices with outdated distances, causing wrong relaxations.

Using settled[] array in modified Dijkstra (k stops). In standard Dijkstra, once a vertex is settled its distance is final. In the k-stops variant, the same vertex can be reached with different numbers of remaining stops — each is a distinct state. Marking vertices as "settled" after first extraction causes incorrect answers.

Integer overflow when dist[u] = INT_MAX. dist[u] + weight overflows if dist[u] == INT_MAX and weight > 0. Always guard with if dist[u] != INT_MAX before relaxation. In Java: use Integer.MAX_VALUE / 2. In Python: use float('inf') which handles arithmetic correctly.

Forgetting to handle unreachable vertices in Network Delay Time. If dist[i] == ∞ for any node, return -1. Not checking this gives the wrong "maximum" (infinity or INT_MAX).

1-indexed vs 0-indexed mismatch. LeetCode problems often use 1-indexed nodes. Build the adjacency list with size n+1 and initialise dist[] with size n+1. Loop from 1 to n (inclusive) when computing the maximum delay. Off-by-one errors here are silent — no crash, just wrong answers.

Interview Questions

Q: Explain the Dijkstra greedy invariant and why it holds only for non-negative weights.

When vertex u is extracted from the min-heap, all other vertices in the heap have distance ≥ dist[u]. Any path to u through an unprocessed vertex v must have total length ≥ dist[v] ≥ dist[u]. Since edge weights are non-negative, extending any path through v can only increase the distance. Therefore no alternative path can improve dist[u] — it's final. With a negative edge w(v,u) < 0, the path source→...→v→u might have total length dist[v] + w(v,u) < dist[u], breaking the invariant.

Q: What is "lazy deletion" in Dijkstra's heap implementation?

Lazy deletion keeps outdated heap entries without removing them. When vertex v's distance is updated, a new (dist[v], v) is pushed into the heap without removing the old (old_dist, v). When the old entry is eventually popped, the check if d > dist[u]: skip detects and discards it. The alternative — decrease-key operation — requires finding and removing the old entry, which is O(V) in a binary heap (or O(log V) with an indexed heap). Lazy deletion is simpler and the extra stale entries add at most E extra heap entries, making total heap size O(E) and total time O(E log E) = O(E log V).

Q: Dijkstra vs BFS for shortest paths — when is each appropriate?

BFS finds shortest paths in unweighted graphs (all edges = weight 1) in O(V+E) — optimal for this case. Dijkstra finds shortest paths in weighted graphs (all weights non-negative) in O((V+E) log V). For an unweighted graph, Dijkstra reduces to BFS (all relaxations give distance + 1). Use BFS when all edge weights are equal; use Dijkstra when edges have different positive weights. For 0-1 weighted graphs, use 0-1 BFS with a deque — it's O(V+E), faster than Dijkstra's O((V+E) log V).

Summary

Dijkstra's algorithm finds single-source shortest paths in O((V+E) log V) using a min-heap. The greedy invariant — extracted vertices have final distances — holds only for non-negative edge weights.

Three implementations:

• ›Heap — O((V+E) log V), best for sparse graphs; standard choice
• ›Array — O(V²), best for dense graphs (E ≈ V²)
• ›Modified — extend state for constrained paths (k stops, k hops)

Key implementation details:

• ›Skip stale entries: if d > dist[u]: continue
• ›Path reconstruction: parent[v] = u when dist[v] updated; backtrack from target
• ›Guard against overflow: check dist[u] != INT_MAX before relaxing

Classic applications:

• ›Network delay time → Dijkstra + max of all distances
• ›Cheapest flights with k stops → Modified Dijkstra with stop counter in state
• ›Single-source shortest path → Standard Dijkstra
• ›All-pairs → Run Dijkstra V times (or use Floyd-Warshall)

In the next topic you will explore Bellman-Ford Algorithm — handling negative edge weights and detecting negative cycles.