Dijkstra’s algorithm

Created in 1956 by Edsger Dijkstra, published in 1959. Single source shortest path problem for non-negative weighted graphs $(G,w)$.

Problem

Input: graph $G=(V,E)$ with weight function $w:E\to {\mathbb{R}}_{\ge 0}$, and a source vertex $s\in V$.

Output: all the shortest paths from $s\to u$ where $u\in V$. $\delta (s,u)$ is defined as the length of shortest path from $s$ to $u$, which is just the sum of the weights on the path.

Imagine that the vertices are ping pong balls, and edges are strings that connect them. Intuitively, Dijkstra’s asks us at each step, how much do we have to pull up by ball $s$ before the next ball leaves the ground? The ball connected to the shortest rope will lift up first, before all other balls.

Structural lemma

Let $S\subset V$ such that for each $u\in S$, it is true that $D(u)=\delta (s,u)$. This is the set of nodes that we’ve already found their shortest paths for.

Suppose that $v\in V-S$ such that $\forall u\in S$, it is true that

$$D(v)\le D(u)+w(u,v)$$

and we pick the $D(v)$ that is the smallest value out of all $v\in V-S$. Then $D(v)=\delta (s,v)$, and we can immediately bring it into $S$.

Proof

Assume that path $p$ is the shortest path $s\to v$. Consider vertex $u$ such that $p:s\to u\to v$, and $(u,v)\in E$. We want to show that $\delta (s,v)=D(v)$. There are two cases:

First case

When $u\in S$, meaning we’ve already found the shortest path for the vertex right before $v$.

Then $D(u)=\delta (s,u)$ is true, so the inequality above is equivalent to $D(v)=\delta (s,u)+w(u,v)$. This is just the definition of the length of $p$, which we’ve already established as a shortest path, and so $D(v)=\delta (s,v)$.

Second case

When $u\in V-S$. Then, the vertex right before $v$ is not in the set $S$, implying that we’ve already crossed over (at least once).

Let $z\in V-S$ be the vertex of where we first crossed over from $S$ to $V-S$. So currently, the path is defined by $s\to z\to u\to v$.

AFC $D(u)>\delta (s,v)$. We know $\delta (s,v)=\delta (s,z)+\delta (z,v)$ from Characterizations about optimal shortest paths, and we know $\delta (s,z)=D(z)$, because this is just the first case:

• We’ve established $s\to z$ to be the shortest path, because of the $\delta (s,z)$ we derived above. This is the assumption.
• There exists a $u^{\prime }$ such that $s\to u^{\prime }\to z$ is a path, $u^{\prime }\in V-S$, and $(u^{\prime },z)\in E$. This has to be true because we defined $z$ to be the first vertex that crossed over.
• See the first case for the rest.

The inequality goes

$$D(u)>\delta (s,v)⟹D(u)>\delta (s,z)+\delta (z,v)⟹D(u)>D(z)+\delta (z,v)$$

This implies $D(u)\ge D(z)$, which means we should have instead chosen vertex $z$ to put into our set $S$ next instead of $v$. This is a contradiction because we know $z\in V-S$ and we chose $v$ instead.

Algorithm

This naturally brings us to an algorithm where at each step, we find this vertex $v\in V-S$, and add it to our set $S$. We then adjust $D(\cdot )$ for all other vertices in $V-S-\{v\}$. We repeat until every vertex is added to $S$, at which point we have discovered $\delta (s,v)$ for all $s\in V$.

Procedure

1. Initialize a set $S$. Store the current distance in a function $D:V\to {\mathbb{R}}_{\ge 0}\cup \{\infty \}$. Set $D(s)=0$ and $D(u)=\infty$ for all other vertices $u\in V-\{s\}$.
2. Keep a min-heap of vertices holding $V-S$, where the keys are $D(v),v\in V-S$.
3. Extract the minimum from the heap. $D(v)$ has become fixed; set $\delta (s,v)\leftarrow D(v)$.
4. For all $z$ such that $(v,z)$ is an edge, we set $D(z)=\min \left\{D(z),D(v)+w(v,z)\right\}$ for the corresponding vertex in the heap.

Proof of correctness

We maintain two loop invariants. At any point in our algorithm, it must be true that

1. $D(v)\ge \delta (s,v)$
2. if $u\in S$ and $v\in V-S$, then $D(v)\le D(u)+w(u,v)$.

Runtime

The algorithm ends when we finish extracting all vertices: there are $n$ such operations. The extracted vertex is operated on exactly once, by iterating over its edges, and possibly relaxing their weights. Then, we will decrease the key of each edge at most once, with $m$ such operations. We have

$$m\log n+n\log n=O((m+n)\log n)$$

Using Fibonacci heaps, we can cut the decrease key operation time down to amortized $O(1)$ time, which means runtime decreases to expected $O(m+n\log n)$.