24. Dijkstra's Algorithm

What you'll learn

• 1Implement Dijkstra with a heap
• 2Skip stale entries with the standard distance-check
• 3Recover the actual path with a parent array

Overview

Dijkstra greedily expands the closest unvisited node. With a binary heap, it runs in O((V + E) log V). It fails on negative weights — use Bellman-Ford or SPFA for those.

Core Concepts

1. Algorithm

1. Initialize dist[start] = 0, all others = infinity.
2. Push (0, start) into a min-heap.
3. Pop the closest node; if its distance is stale (greater than dist[u]), skip.
4. For each neighbor v with edge weight w, if dist[u] + w < dist[v], update and push.
5. Repeat until the heap is empty.

2. Standard implementation

import heapq

def dijkstra(start, adj, n):
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue              # stale entry
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

3. Why we don't need a visited array

The `if d > dist[u]: continue` check skips stale entries that were pushed when a shorter path hadn't been found yet. This is cleaner than maintaining a separate visited set.

4. Reconstructing the path

parent = [-1] * (n + 1)
# ... in the relaxation step ...
if nd < dist[v]:
    dist[v] = nd
    parent[v] = u
    heapq.heappush(heap, (nd, v))

def reconstruct(target):
    path = []
    cur = target
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    return path[::-1]

5. When NOT to use Dijkstra

• Negative edges → Bellman-Ford or SPFA
• Negative cycles → no shortest path exists
• All edges weight 1 → use BFS (simpler)
• Dense graphs with V² edges → may be faster with adjacency matrix + O(V²)

Examples

Example 1 — src/01_dijkstra.py

Standard Dijkstra returning a dist array.

Example 2 — src/02_dijkstra_path.py

Dijkstra with path reconstruction.

Example 3 — src/03_dijkstra_grid.py

Dijkstra on a 2D grid where moving has variable cost.

Example 4 — src/04_dijkstra_compare.py

Compare BFS vs Dijkstra: same answer on unweighted, BFS is faster.

Common Mistakes

1. Running Dijkstra on a graph with negative weights — silent wrong answers.
2. Pushing (node, dist) instead of (dist, node) — heap sorts by first element!
3. Forgetting the stale-entry check → can explode to O(VE log V).
4. Using sys.maxsize and getting overflow in dense graphs — use float('inf').

Recap

• Dijkstra: heap + dist array + stale check.
• O((V + E) log V) with binary heap.
• No negative weights.

Try It

1. BOJ 1753 (Shortest path).
2. BOJ 1916 (Minimum cost).
3. BOJ 1238 (Party).