Graph Algorithms contents

Dijkstra's Algorithm

Shortest paths from one source in a graph with non-negative weights, in O((n + m) log n) with a heap, plus path restoration.

Intermediate7 min readdijkstrashortest pathheapweighted graphs

Read first: Breadth-First Search, Heaps, Deques and Bisect

You are given a directed or undirected weighted graph with $n$ vertices and $m$ edges, all weights non-negative, and a source vertex $s$ . Dijkstra's algorithm finds the length of the shortest path from $s$ to every other vertex (the single-source shortest paths problem), and the paths themselves. It was described by Edsger Dijkstra in 1959.

Algorithm

Keep an array $d[v]$ with the length of the best path found so far from $s$ to $v$ . Initially $d[s] = 0$ and $d[v] = \infty$ for the rest. Repeat:

Among the vertices not yet finalized, pick $v$ with the smallest $d[v]$ and finalize it.
Relax all edges $(v, u)$ with weight $w$ : if $d[v] + w < d[u]$ , set $d[u] = d[v] + w$ .

The idea is that the closest unfinalized vertex can't be improved anymore: any other route to it would have to leave through some unfinalized vertex which is at least as far, and weights are non-negative.

Proof sketch

Claim: when $v$ is finalized, $d[v]$ is the true shortest distance. Suppose a shorter path $P$ to $v$ existed. It must leave the set of finalized vertices at some edge $(q, p)$ with $q$ finalized and $p$ not. By induction $d[q]$ was exact, so after relaxing from $q$ , $d[p] \le \text{len}(P \text{ up to } p) \le \text{len}(P) < d[v]$ , contradicting the choice of $v$ as the minimum.

The proof uses non-negative weights in " $\text{len}(P \text{ up to } p) \le \text{len}(P)$ ". With negative edges the algorithm can return wrong answers: use Bellman-Ford.

Implementation with a heap

Finding the minimum by scanning is $O(n)$ per step, giving $O(n^2)$ overall. With a binary heap (heapq) the minimum comes out in $O(\log n)$ . Python's heap has no "decrease key", so we use lazy deletion: push a new (distance, vertex) entry each time we improve a distance, and skip stale entries when they are popped.

python

import heapq

INF = float("inf")

def dijkstra(adj, s):
    """adj[v] = list of (neighbour, weight). Return (dist, parent)."""
    n = len(adj)
    dist = [INF] * n
    parent = [-1] * n
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        d, v = heapq.heappop(heap)
        if d > dist[v]:                       # stale entry: a shorter path was found later
            continue
        for u, w in adj[v]:
            nd = d + w
            if nd < dist[u]:
                dist[u] = nd
                parent[u] = v
                heapq.heappush(heap, (nd, u))
    return dist, parent

adj = [
    [(1, 7), (2, 9), (5, 14)],       # 0
    [(0, 7), (2, 10), (3, 15)],      # 1
    [(0, 9), (1, 10), (3, 11), (5, 2)],
    [(1, 15), (2, 11), (4, 6)],
    [(3, 6), (5, 9)],
    [(0, 14), (2, 2), (4, 9)],
]
dist, parent = dijkstra(adj, 0)
assert dist == [0, 7, 9, 20, 20, 11]

Complexity. Each edge causes at most one push, so the heap holds $O(m)$ entries and the total is $O((n + m)\log n)$ (or $O(m \log n)$ for connected graphs). Memory $O(n + m)$ .

Restoring a shortest path

Like BFS, follow parent pointers back from the target:

python

def restore_path(parent, t):
    path = []
    while t != -1:
        path.append(t)
        t = parent[t]
    return path[::-1]

assert restore_path(parent, 4) == [0, 2, 5, 4]
assert restore_path(parent, 0) == [0]

Early exit

If you only need the distance to one target $t$ , stop as soon as $t$ is popped: its distance is final.

Checking it

Compare with a different algorithm (Bellman-Ford) on random graphs:

python

import random

def bellman_ford_simple(n, edges, s):
    dist = [INF] * n
    dist[s] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

random.seed(7)
for _ in range(300):
    n = random.randint(1, 10)
    edges = [(random.randrange(n), random.randrange(n), random.randint(0, 9)) for _ in range(random.randint(0, 25))]
    g = [[] for _ in range(n)]
    for u, v, w in edges:
        g[u].append((v, w))
    s = random.randrange(n)
    assert dijkstra(g, s)[0] == bellman_ford_simple(n, edges, s)

Dense graphs: $O(n^2)$ without a heap

For a dense graph ( $m \approx n^2$ ), the heap does not help: pick the minimum by a linear scan and relax from an adjacency matrix. The cost is $O(n^2)$ , which beats $O(m \log n)$ when $m \gg n^2/\log n$ .

python

def dijkstra_dense(matrix, s):
    """matrix[u][v] = weight or INF if there is no edge."""
    n = len(matrix)
    dist = [INF] * n
    dist[s] = 0
    done = [False] * n
    for _ in range(n):
        v = -1
        for u in range(n):
            if not done[u] and (v == -1 or dist[u] < dist[v]):
                v = u
        if dist[v] == INF:
            break
        done[v] = True
        row = matrix[v]
        for u in range(n):
            if dist[v] + row[u] < dist[u]:
                dist[u] = dist[v] + row[u]
    return dist

n = len(adj)
mat = [[INF] * n for _ in range(n)]
for v in range(n):
    for u, w in adj[v]:
        mat[v][u] = min(mat[v][u], w)
assert dijkstra_dense(mat, 0) == dist

Pitfalls

Negative weights break correctness. A zero-weight edge is fine.
Use float("inf") (or a value larger than any possible path) as infinity. Adding to inf stays inf, so no special handling is needed in Python.
The stale-entry check if d > dist[v]: continue is essential for the stated complexity: without it, a vertex may be expanded many times.
Unreachable vertices keep dist == INF.
If all weights are equal use BFS; if they are only $0$ or $1$ use 0-1 BFS.

Algorithm

Proof sketch

Implementation with a heap

Restoring a shortest path

Early exit

Checking it

Dense graphs: O(n2)O(n^2)O(n2) without a heap

Pitfalls

Practice problems

Dense graphs: $O(n^2)$ without a heap