Module 21 · Union-Find, Weighted Graphs, and Minimum Spanning Trees

207. Dijkstra Shortest Paths

Bridge · Download this solution · All solutions and shared helpers

Problem

Compute shortest distances from source in a directed weighted adjacency list, where each entry is (neighbor,nonnegative_weight). Vertices and source are valid indices; parallel edges and zero weights are allowed. Return a list with None for unreachable vertices. Negative weights are outside the contract.

Examples

Example 1

dijkstra([[(1,10),(2,1)],[],[(1,2)],[]],0)
=> [0, 3, 1, None]

A later proposal improves vertex 1 while vertex 3 remains unreachable.

Example 2

dijkstra([[(1,0)],[]],0)
=> [0, 0]

Zero-cost edges are permitted.

Example 3

dijkstra([[]],0)
=> [0]

The source has a zero-edge route to itself.

Reveal the worked solution and reasoning

Why this mechanism works

Use a min-heap of proposed total path distances. Relaxing an edge offers a better route to its destination. Since Python's heap has no decrease-key operation, push the new proposal and leave old entries to be skipped later. Nonnegative edges ensure the smallest current proposal cannot be improved through a farther unsettled vertex.

State and boundaries

dist[v] is the best route length discovered so far. A heap entry is actionable only when its distance still equals dist[v].

Protocol

Initialize infinity everywhere except source zero.
Pop the minimum proposal.
Skip a stale distance.
Relax each outgoing edge with current distance+weight.
Push every strict improvement.
Convert remaining infinities to None.

Visualization

0->1 cost 10; 0->2 cost 1; 2->1 cost 2
proposals for 1: 10, then 3
pop 3 and finalize; later 10 is stale

Python implementation

import heapq

def dijkstra(adj, source):
    dist = [float('inf')] * len(adj)
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        distance, u = heapq.heappop(heap)
        if distance != dist[u]:
            continue
        for v, weight in adj[u]:
            candidate = distance + weight
            if candidate < dist[v]:
                dist[v] = candidate
                heapq.heappush(heap, (candidate, v))
    return [None if value == float('inf') else value for value in dist]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

dijkstra([[(1,10),(2,1)],[],[(1,2)],[]],0)

L4 dijkstra: dist = [float('inf')] * len(adj)
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[inf, inf, inf, inf]

L5 dijkstra: dist[source] = 0
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, inf, inf, inf]

L6 dijkstra: heap = [(0, source)]
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, inf, inf, inf]; heap=[(0, 0)]

L8 dijkstra: distance, u = heapq.heappop(heap)
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, inf, inf, inf]; heap=[]; distance=0; u=0

L11 dijkstra: for v, weight in adj[u]:
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, inf, inf, inf]; heap=[]; distance=0; u=0; v=1; weight=10

L12 dijkstra: candidate = distance + weight
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, inf, inf, inf]; heap=[]; distance=0; u=0; v=1; weight=10; candidate=10

L14 dijkstra: dist[v] = candidate
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, 10, inf, inf]; heap=[]; distance=0; u=0; v=1; weight=10; candidate=10

L15 dijkstra: heapq.heappush(heap, (candidate, v))
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, 10, inf, inf]; heap=[(10, 1)]; distance=0; u=0; v=1; weight=10; candidate=10

... 12 intermediate state changes omitted ...

L16 dijkstra: return [None if value == float('inf') else value for value in dist]
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, 3, 1, inf]; heap=[]; distance=10; u=1; v=1; weight=2; candidate=3; value=3

L16 dijkstra: return [None if value == float('inf') else value for value in dist]
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, 3, 1, inf]; heap=[]; distance=10; u=1; v=1; weight=2; candidate=3; value=1

L16 dijkstra: return [None if value == float('inf') else value for value in dist]
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, 3, 1, inf]; heap=[]; distance=10; u=1; v=1; weight=2; candidate=3; value=inf

L16 dijkstra: return [None if value == float('inf') else value for value in dist]
adj=[[(..., ...), (..., ...)], [], [(..., ...)], []]; source=0; dist=[0, 3, 1, inf]; heap=[]; distance=10; u=1; v=1; weight=2; candidate=3

Result: [0, 3, 1, None]. A later proposal improves vertex 1 while vertex 3 remains unreachable.

dijkstra([[(1,0)],[]],0)

L4 dijkstra: dist = [float('inf')] * len(adj)
adj=[[(..., ...)], []]; source=0; dist=[inf, inf]

L5 dijkstra: dist[source] = 0
adj=[[(..., ...)], []]; source=0; dist=[0, inf]

L6 dijkstra: heap = [(0, source)]
adj=[[(..., ...)], []]; source=0; dist=[0, inf]; heap=[(0, 0)]

L8 dijkstra: distance, u = heapq.heappop(heap)
adj=[[(..., ...)], []]; source=0; dist=[0, inf]; heap=[]; distance=0; u=0

L11 dijkstra: for v, weight in adj[u]:
adj=[[(..., ...)], []]; source=0; dist=[0, inf]; heap=[]; distance=0; u=0; v=1; weight=0

L12 dijkstra: candidate = distance + weight
adj=[[(..., ...)], []]; source=0; dist=[0, inf]; heap=[]; distance=0; u=0; v=1; weight=0; candidate=0

L14 dijkstra: dist[v] = candidate
adj=[[(..., ...)], []]; source=0; dist=[0, 0]; heap=[]; distance=0; u=0; v=1; weight=0; candidate=0

L15 dijkstra: heapq.heappush(heap, (candidate, v))
adj=[[(..., ...)], []]; source=0; dist=[0, 0]; heap=[(0, 1)]; distance=0; u=0; v=1; weight=0; candidate=0

L8 dijkstra: distance, u = heapq.heappop(heap)
adj=[[(..., ...)], []]; source=0; dist=[0, 0]; heap=[]; distance=0; u=1; v=1; weight=0; candidate=0

L16 dijkstra: return [None if value == float('inf') else value for value in dist]
adj=[[(..., ...)], []]; source=0; dist=[0, 0]; heap=[]; distance=0; u=1; v=1; weight=0; candidate=0; value=0

L16 dijkstra: return [None if value == float('inf') else value for value in dist]
adj=[[(..., ...)], []]; source=0; dist=[0, 0]; heap=[]; distance=0; u=1; v=1; weight=0; candidate=0

Result: [0, 0]. Zero-cost edges are permitted.

Why the solution is correct

Every finite proposal is the length of an actual path. At a nonstale minimum pop, any competing route through an unsettled vertex must already be at least that large because remaining edge weights are nonnegative. Thus the popped distance is final. Relaxations then preserve all candidate shortest routes.

Time and space

O(V+E log(E+2)) time and O(V+E) auxiliary space for a lazy heap that can hold multiple proposals per vertex. With simple graphs this is commonly written O((V+E) log V).

Common mistakes

Using edge weight alone as the priority runs an MST-style rule, not shortest paths. A permanent visited mark at first enqueue is too early. Negative edges break the finalization proof.

Reasoning card

State: dist[v] is the best route length discovered so far. A heap entry is actionable only when its distance still equals dist[v].

Invariant: A popped non-stale distance is final.

Decision to rehearse: Heap exposes the unsettled node with smallest known distance.

Finish: Convert remaining infinities to None

Transfer exercise

Return predecessor pointers alongside distances, and explain how equal-cost ties affect the chosen path.