Dijkstra's Algorithm

1Introduction

This lecture explains how Dijkstra's algorithm computes single-source shortest-path distances in a graph with nonnegative edge weights. It defines tentative distances, settled vertices, and relaxation, then proves correctness through a loop invariant and a cut argument.

2Problem setting

Let $$G=(V,E)$$G=(V,E) be a finite directed or undirected graph, let $$s\in V$$s\in V be the source, and let $$w:E\to R_{\text{[PARSE ERROR: Undefined("Command("ge")")]}0}$$w:E\to\mathbb{R}_{\ge 0} be the weight function. The length of a path is the sum of its edge weights. Write $$\delta (s,v)$$\delta(s,v) for the shortest-path distance from $$s$$s to $$v$$v, with $$\delta (s,v)=\mathrm{\infty }$$\delta(s,v)=\infty when $$v$$v is unreachable from $$s$$s.

3Terminology

• The tentative distance $$d\left[v\right]$$d[v] is the minimum length among the currently discovered paths from $$s$$s to $$v$$v. It is $$\mathrm{\infty }$$\infty if no such path has been discovered. Consequently, $$\delta (s,v)\text{[PARSE ERROR: Undefined("Command("le")")]}d\left[v\right]$$\delta(s,v)\le d[v] always holds.
• The settled set $$S$$S consists of vertices for which $$d\left[v\right]=\delta (s,v)$$d[v]=\delta(s,v) has been proved. Such a vertex is called settled.
• To relax an edge $$(u,v)$$(u,v) is to assign $$d\left[v\right]\leftarrow d\left[u\right]+w(u,v)$$d[v]\leftarrow d[u]+w(u,v) whenever $$d\left[u\right]+w(u,v)<d\left[v\right]$$d[u]+w(u,v)<d[v].
• A priority queue extracts a vertex with minimum $$d$$d among unsettled candidates.

4Algorithm

Initialize $$d\left[s\right]=0$$d[s]=0, $$d\left[v\right]=\mathrm{\infty }$$d[v]=\infty for $$v\ne s$$v\ne s, and $$S=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$S=\varnothing. Insert $$(0,s)$$(0,s) into a priority queue. Repeat the following steps until the queue is empty.

1. Extract a pair $$(x,u)$$(x,u) with minimum distance key.
2. If $$u\in S$$u\in S or $$x\ne d\left[u\right]$$x\ne d[u], discard this obsolete pair.
3. Otherwise, add $$u$$u to $$S$$S and relax every outgoing edge $$(u,v)$$(u,v) for which $$v\notin S$$v\notin S. Whenever $$d\left[v\right]$$d[v] decreases, insert the new pair $$\left(d\right[v],v)$$(d[v],v).

An implementation that leaves old distance keys in the queue can contain several entries for one vertex. Such an obsolete pair is a stale entry. The test in step 2 permits a correct heap implementation without a decrease-key operation.

5Loop invariant

At the beginning of every iteration, the following statements hold.

1. For every $$u\in S$$u\in S, $$d\left[u\right]=\delta (s,u)$$d[u]=\delta(s,u).
2. For every $$v\notin S$$v\notin S, $$d\left[v\right]$$d[v] is the minimum length of an $$s$$s-to-$$v$$v path whose vertices other than $$v$$v belong to $$S$$S. When $$v\ne s$$v\ne s, this is equivalent to requiring that its internal vertices lie in $$S$$S and its final edge cross from $$S$$S to $$v$$v. If no such path exists, then $$d\left[v\right]=\mathrm{\infty }$$d[v]=\infty.

Initially, only the length-zero path to $$s$$s is a candidate, so the invariant holds. Relaxing every outgoing edge of a newly settled vertex records exactly the new candidate paths made available by using vertices of $$S$$S internally. Hence statement 2 is preserved.

6Correctness of settling

Let $$u$$u be an unsettled vertex with minimum $$d$$d. If $$u=s$$u=s, then $$d\left[s\right]=0=\delta (s,s)$$d[s]=0=\delta(s,s). Otherwise, suppose that $$u$$u is reachable, and choose a shortest path $$P$$P from $$s$$s to $$u$$u. Let $$(y,z)$$(y,z) be the first edge of $$P$$P that leaves $$S$$S. Reasoning across this boundary is the cut argument.

Let $$c\left(P\right[s:y\left]\right)$$c(P[s:y]) denote the length of the prefix of $$P$$P from $$s$$s to $$y$$y. Because $$y\in S$$y\in S, the invariant and the relaxation of $$(y,z)$$(y,z) imply

All edge weights are nonnegative, so adding the suffix of $$P$$P after $$z$$z cannot decrease its length. Thus

The choice of $$u$$u gives $$d\left[u\right]\text{[PARSE ERROR: Undefined("Command("le")")]}d\left[z\right]$$d[u]\le d[z], while a tentative distance is the length of an actual path and therefore $$\delta (s,u)\text{[PARSE ERROR: Undefined("Command("le")")]}d\left[u\right]$$\delta(s,u)\le d[u]. Consequently,

which proves $$d\left[u\right]=\delta (s,u)$$d[u]=\delta(s,u). Settling $$u$$u therefore preserves statement 1 of the invariant.

7Unreachable vertices

When the queue becomes empty, every vertex reachable from $$s$$s has been settled. An unreachable vertex is never inserted, so its value remains $$d\left[v\right]=\mathrm{\infty }$$d[v]=\infty. There is no need to extract or settle candidates whose keys are infinite.

8Why negative edges are forbidden

Consider edges $$s\to u$$s\to u of weight 2, $$s\to v$$s\to v of weight 5, and $$v\to u$$v\to u of weight -4. Dijkstra's algorithm settles $$u$$u with $$d\left[u\right]=2$$d[u]=2 before $$v$$v with $$d\left[v\right]=5$$d[v]=5. However, the path $$s\to v\to u$$s\to v\to u has length 1, so the true distance is $$\delta (s,u)=1$$\delta(s,u)=1. A negative edge can decrease a path length after the path crosses the cut, invalidating the inequality in the proof that depends on nonnegativity.

9Complexity

With adjacency lists and a binary heap, each directed edge is relaxed at most once. An undirected edge occurs in the adjacency lists of both endpoints and is examined at most once in each direction. Each successful relaxation inserts at most one pair. The running time is

which is commonly written as $$O\left(\right|E\left|\log \right|V\left|\right)$$O(|E|\log |V|) when every vertex is reachable from the source. An implementation that retains stale entries uses $$O\left(\right|V|+|E\left|\right)$$O(|V|+|E|) auxiliary space. An implementation with decrease-key can keep the queue size at $$O\left(\right|V\left|\right)$$O(|V|).

10Summary

• Dijkstra's algorithm requires every edge weight to be nonnegative.
• The loop invariant and cut argument justify settling a vertex with minimum tentative distance.
• Stale entries, unreachable vertices, and the supported heap operations must be stated as part of the implementation contract.