Dijkstra’s Algorithm

Dijkstra’s algorithm computes the single-source shortest path in a graph with non-negative edge weights, in O((V + E) log V) time using a binary heap. It’s the algorithmic backbone of GPS routing, network packet routing (OSPF), game pathfinding, and anything that asks “what’s the cheapest way from A to B with weighted edges?” The algorithm is greedy: at each step, it commits to the closest unvisited vertex and never looks back — a commitment that’s only safe because all edge weights are non-negative.

1. Intuition — GPS Routing Explained

Imagine you’re a GPS computing the fastest route from your house to the airport.

• You start at your house. The “shortest distance to your house” is 0; to everywhere else, infinity (we haven’t found any route yet).
• You look at every intersection directly reachable from your house, and update their tentative distances to “distance via the road I’m sitting on.”
• Now: which intersection is closest? Maybe a corner store 0.3 miles away. Whatever its distance is, that’s its final, true shortest distance — because every other route to it would have to travel a longer path to some unvisited intersection first, and all unvisited intersections are at least as far away.
• “Settle” the corner store. From there, look at its outgoing roads, and update your tentative distances again. Maybe now the gas station is 0.5 miles via corner-store, beating its previous estimate of 0.7 via a different route.
• Repeat: pick the closest unsettled intersection, settle it, update its neighbors.
• Eventually you settle the airport. Done.

This greedy strategy works because edge weights are non-negative. If some road had a negative length (say, a teleporter that gives back time), then settling the corner store too early would be wrong — a longer-then-negative detour might beat the direct route. That’s why Dijkstra needs non-negative weights; for negative weights, use Bellman-Ford.

2. Tiny Worked Example

Find shortest paths from A to all other vertices in this weighted graph:

        7
    A ─────── B
    │         │
   2│        3│
    │         │
    C ─────── D
        1
    │         │
   5│        2│
    │         │
    E ─────── F
        4

Edges (undirected):

A–B: 7,  A–C: 2,  B–D: 3,  C–D: 1,  C–E: 5,  D–F: 2,  E–F: 4

Trace Dijkstra from A:

Step	Settled	Distances (A,B,C,D,E,F)	Heap (after step)	Action
0	{}	(0, ∞, ∞, ∞, ∞, ∞)	[(0,A)]	start
1	{A}	(0, 7, 2, ∞, ∞, ∞)	[(2,C), (7,B)]	settle A; relax to B(7), C(2)
2	{A,C}	(0, 7, 2, 3, 7, ∞)	[(3,D), (7,B), (7,E)]	settle C; relax to D(2+1=3), E(2+5=7)
3	{A,C,D}	(0, 6, 2, 3, 7, 5)	[(5,F), (6,B), (7,B-stale), (7,E)]	settle D; relax to B(3+3=6 < 7), F(3+2=5)
4	{A,C,D,F}	(0, 6, 2, 3, 7, 5)	[(6,B), (7,B-stale), (7,E), (9,E-stale)]	settle F; relax to E(5+4=9, no improvement; E is still 7)
5	{A,C,D,F,B}	(0, 6, 2, 3, 7, 5)	[(7,B-stale), (7,E), (9,E-stale)]	settle B; no improvements
6	{A,C,D,F,B,E}	(0, 6, 2, 3, 7, 5)	[(9,E-stale)]	settle E; done

Final distances: A=0, B=6, C=2, D=3, E=7, F=5. The “B-stale” entries with distance 7 are leftover from before D was settled (which improved B from 7 to 6); when we later pop them, we check the recorded distance and see they’re stale, so we skip.

3. Pseudocode

dijkstra(graph, source):
    dist := map from each vertex to ∞
    dist[source] := 0
    heap := empty min-heap
    push (0, source) onto heap
    while heap is not empty:
        (d, u) := pop min from heap
        if d > dist[u]:
            continue                          # stale entry; skip
        for each (v, w) in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] := dist[u] + w
                push (dist[v], v) onto heap
    return dist

The “stale check” (if d > dist[u]) is what lets us avoid maintaining a decrease-key operation on the heap — instead, we push duplicate entries with updated distances and skip any popped entry whose distance is already beaten.

4. Python — Idiomatic with heapq

import heapq
 
def dijkstra(graph, source):
    """graph: dict node -> list of (neighbor, weight). Returns dist map."""
    dist = {source: 0}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                           # stale
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Reconstructing the path

def dijkstra_with_parent(graph, source):
    dist = {source: 0}
    parent = {source: None}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, parent
 
def reconstruct(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

Single-target early termination

If you only want the distance to one specific target, you can break as soon as you pop it from the heap (its distance is final). This often gives a substantial speedup.

def dijkstra_target(graph, source, target):
    dist = {source: 0}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if u == target: return d              # early exit!
        if d > dist[u]: continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return float('inf')                        # unreachable

5. Why It Works (Greedy Correctness Proof)

Claim: when we pop (d, u) from the heap and d == dist[u] (not stale), then dist[u] is the true shortest-path distance from source to u.

Proof sketch (exchange argument). Suppose for contradiction there’s a shorter path from source to u than dist[u]. That path goes through some vertex v that’s not yet settled — call its first such vertex v*. The path’s length up to v* is some value d_v*. Since v* precedes u on this hypothetical shorter path, d_v* ≤ shorter_path < dist[u]. But we picked u as the minimum-distance unsettled vertex, so dist[u] ≤ dist[v*] ≤ d_v* — a contradiction.

The proof relies critically on non-negative weights — without them, “the path’s length up to v*” might exceed the full path’s length (because subsequent edges could be negative). With negative weights, settling u early is unsafe, and the algorithm gives wrong answers silently.

6. Complexity

Heap implementation	Time
Array (no heap)	O(V²) — V extract-min ops at O(V) each
Binary heap	O((V + E) log V)
Fibonacci heap	O(E + V log V)

Dense vs sparse graphs:

• Sparse (E = O(V)): binary-heap Dijkstra is O(V log V) — fast.
• Dense (E = O(V²)): O(V² log V) is worse than the array version’s O(V²). Use the array version for dense graphs.

Why the duplicate-push approach is still O((V+E) log V). Each edge can produce at most one push to the heap — so the heap holds at most O(E) entries. Each push and pop is O(log E) = O(log V²) = O(log V). Total: O(E log V) for heap ops plus O(V log V) for the V relevant extract-mins, giving O((V+E) log V).

Decrease-key vs lazy deletion

Textbook Dijkstra uses a heap with decrease_key operation. Real implementations almost always use the “lazy” variant — push duplicate entries, skip stale on pop — because it avoids needing a value → heap-position index. The complexity is asymptotically the same; constants differ slightly.

7. Variants

7.1 Dijkstra on a Grid

Many interview problems are “shortest path through a grid where each cell has a cost.” Treat each cell as a vertex; neighbors are 4 (or 8) adjacent cells; edge weight = entering cost. Apply standard Dijkstra. The graph is implicit (no need to build the adjacency list).

def shortest_path_grid(grid):
    rows, cols = len(grid), len(grid[0])
    dist = {(0, 0): grid[0][0]}
    heap = [(grid[0][0], 0, 0)]
    DIR = [(-1,0),(1,0),(0,-1),(0,1)]
    while heap:
        d, r, c = heapq.heappop(heap)
        if (r, c) == (rows-1, cols-1): return d
        if d > dist[(r, c)]: continue
        for dr, dc in DIR:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                nd = d + grid[nr][nc]
                if nd < dist.get((nr, nc), float('inf')):
                    dist[(nr, nc)] = nd
                    heapq.heappush(heap, (nd, nr, nc))

7.2 Multiple Sources

To find shortest distance from “the nearest of several sources,” initialize the heap with all sources at distance 0 (or their respective initial distances). Same algorithm; one run.

7.3 A* Search

A* is Dijkstra plus a heuristic. Push (g + h, vertex) where g is the actual cost-so-far and h is an admissible (≤ true remaining cost) heuristic estimate. With a perfect heuristic, A* explores only the optimal path; with a zero heuristic, A* degenerates to Dijkstra. Critical for game pathfinding (Manhattan distance heuristic on grids) and routing.

7.4 Bidirectional Dijkstra

Run Dijkstra simultaneously from source and target, alternating one expansion from each side; stop when the two frontiers meet. Often dramatically faster on huge graphs (e.g., road networks).

7.5 0-1 BFS as a Special Case

When all edge weights are in {0, 1}, a deque-based BFS (push 0-weight edges to the front, 1-weight to the back) computes shortest paths in O(V+E) — beating Dijkstra’s O((V+E) log V). See 01-BFS.

7.6 Johnson’s Algorithm

For all-pairs shortest paths on a graph with negative edges (but no negative cycle): use Bellman-Ford from a virtual source to compute vertex potentials, reweight edges to be non-negative, then run Dijkstra from each vertex. Total O(V² log V + VE). See Johnson’s Algorithm.

8. When To Use Dijkstra

8.1 Use Dijkstra when:

• Edge weights are non-negative (the absolute prerequisite).
• You need shortest paths from one source.
• Graph is moderately-to-large with non-trivial weights.

8.2 Use something else when:

• Negative weights exist → Bellman-Ford (handles negatives, also detects negative cycles).
• Edges all have weight 1 → Breadth-First Search is O(V+E), simpler.
• Edges in {0, 1} → 01-BFS is O(V+E).
• All-pairs shortest paths needed → Floyd-Warshall for O(V³) (faster than V Dijkstras when graph is dense and you need every pair).
• Heuristic available → A* Search is faster.

9. Common Interview Problems

Problem	Pattern
LC 743 — Network Delay Time	Plain Dijkstra
LC 787 — Cheapest Flights Within K Stops	Modified Dijkstra (extra state for stop count) — sometimes Bellman-Ford fits better
LC 1631 — Path with Minimum Effort	Dijkstra on grid where edge cost is max instead of sum
LC 1514 — Path with Maximum Probability	Dijkstra with multiplication; use -log(prob) as edge weight to convert to additive shortest-path
LC 778 — Swim in Rising Water	Dijkstra/binary-search on grid
LC 1334 — Find the City With the Smallest Number of Neighbors at a Threshold Distance	Floyd-Warshall (all-pairs) usually cleaner
LC 1976 — Number of Ways to Arrive at Destination	Dijkstra with path counting
Currency arbitrage / shortest exchange path	Dijkstra-vs-Bellman-Ford decision based on cost sign

10. Pitfalls

10.1 Negative Edge Weights

Dijkstra silently gives wrong answers on graphs with negative edges. There’s no warning, no exception — just incorrect output. If you suspect negative weights might appear, validate or use Bellman-Ford. The trap is especially common in problems where weights are derived (e.g., “cost = a - b” can go negative).

10.2 Naive decrease-key Without Index Map

Implementing decrease_key properly requires a vertex → heap_position map. Without it, you can’t find the entry to update. The lazy-deletion variant (push duplicate, skip stale) sidesteps this.

10.3 Stale Entries Not Skipped

while heap:
    d, u = heapq.heappop(heap)
    # WRONG: missing stale-skip check
    for v, w in graph[u]:
        ...

Without the if d > dist[u]: continue check, you process the same vertex multiple times — correctness is preserved but you do up to E re-processings. Total time degrades from O((V+E) log V) to O((V+E)² log V) worst case.

10.4 Using dist.get(v, float('inf')) vs Pre-Filling

If you initialize dist with {u: float('inf') for u in graph} then iterate for v, w in graph[u], you’ll fail on neighbors not in the initial dict. Either pre-fill all vertices or use .get(v, ∞). Easy bug.

10.5 Counting Edges When Should Count Hops

A frequent variant problem (“cheapest flight within K stops”) needs both cost and hop count tracked in the state. Plain Dijkstra ignoring hop count gives wrong answers because a cheaper-but-longer path can be settled first and block the cheaper-within-K path. Solutions: include (cost, hops, node) in the heap, or use Bellman-Ford (which naturally enforces edge-relaxation rounds).

10.6 Maximum Spanning Tree by Negation

People sometimes try to use Dijkstra for “max-cost path” by negating weights. This breaks Dijkstra (now there are negative weights). Use a different formulation: max-flow, longest-path-on-DAG, or modified relaxation if structure permits.

10.7 Forgetting to Return Distance to Source as 0

Edge case: dist[source] = 0 not handled → returns inf for source.

10.8 Heap Comparator and Tuple Ordering

When tuples include non-comparable items (e.g., (distance, custom_object)), Python raises TypeError on tied distances. Add a tiebreaker: (distance, counter, item).

11. Diagram — Dijkstra’s Frontier

flowchart LR
  S[(Source<br/>dist=0<br/>SETTLED)] --> A[(A<br/>dist=2<br/>SETTLED)]
  S --> B[(B<br/>dist=7<br/>tentative)]
  A --> C[(C<br/>dist=3<br/>tentative)]
  A --> D[(D<br/>dist=5<br/>tentative)]
  B -.relax candidate.-> X[(X<br/>dist=∞)]
  C -.relax candidate.-> X

What this diagram shows. Settled vertices (Source, A) have final distances. Tentative vertices (B, C, D) have current best estimates that may still improve as more neighbors are explored. The heap holds the tentative-vertex entries; the next pop will be the smallest-tentative (here C at distance 3), which then becomes settled. The frontier expands outward in non-decreasing distance order — this is the “wave” that gives Dijkstra its correctness guarantee.

12. Real-World Use

• GPS / map routing: Google Maps, Waze, etc. use Dijkstra (with massive precomputation: contraction hierarchies, transit node routing).
• Network packet routing: OSPF (Open Shortest Path First) — routers run Dijkstra on link-state databases to compute next-hops.
• Game pathfinding: typically A* Search (Dijkstra plus heuristic) on tile grids.
• Telephone network routing (historical): minimize call cost.
• Robotic motion planning: shortest path in configuration space.

13. Open Questions

• When does a Fibonacci heap actually beat a binary heap in practice for Dijkstra? Almost never — the constant factors dwarf the theoretical advantage on real inputs.
• How do contraction hierarchies achieve sub-linear-per-query routing on continent-scale road graphs? Beyond interview scope; worth a separate note.

14. See Also

• Bellman-Ford — handles negative edges; detects negative cycles
• Floyd-Warshall — all-pairs shortest paths
• A* Search — heuristic-guided Dijkstra
• Johnson’s Algorithm — all-pairs with negative edges
• 01-BFS — special case for {0,1}-weight graphs
• Bidirectional BFS — meet-in-the-middle approach
• Binary Heap — the data structure Dijkstra is built on
• Breadth-First Search — unweighted shortest path
• Big-O Notation
• SWE Interview Preparation MOC