Dijkstra's Algorithm

Input Directed weighted graph with non-negative weights and a source node

Output The shortest path and length from the source node to every other

Dijkstra's algorithm starts at the source node and selects the unexplored node which results in a shortest path at each step.

Dijkstra's algorithm can be represented in pseudocode as follows

s = start node
G = (V, E) = graph
S = {s} = set of explored vertices
d = shortest path distance
d(s) = 0
while S != V
    select v not in S which minimises d'(v)
    add v to S and let d(v) = d'(v)

where $d'(v) = \min_{e = (u,v):u\in S} d(u) + \ell_e$.

To produce the shortest paths the edge chosen at each step should be recorded when $v$ is added to $S$. Then to find the shortest path to some node $x$ look at the edge chosen, $(y,x)$, for example. Then look at the edge chosen for $y$ and recursively follow the path back to the source.

Proof of correctness

Dijkstra's is correct if after each iteration $\forall u \in S$, $P_u$ is a shortest path from $s$ to $u$ and $d(u) = \ell(P_u)$.

This can be proven by induction on the size of $S$.

Base case $|S| = 1$, $S = {s}$ and $d(s) = 0$

Inductive case Suppose the claim holds when $|S| = k$ for some $k \geq 1$.

For $|S| = k+1$, add the node $v$. Let $(u,v)$ be the final edge of the path $P_v$. By the inductive hypothesis, $P_u$ is the shortest path for each $u \in S$.

Consider any other $s$-$v$ path $P$. In order to reach $v$, $P$ must leave $S$ somewhere. Let $y$ be the first node on $P$ that is not in $S$ and $x \in S$ be the node just before $y$.

Let $P'$ be the subpath of $P$ from $s$ to $x$. Since $x \in S$, $P_x$ is the shortest path and has length $d(x)$ by the inductive hypothesis. Therefore $\ell(P') \geq \ell(P_x) = d(x)$.

Therefore $\ell(P) \geq \ell(P') + \ell(x,y) \geq d(x) + \ell(x,y) \geq d'(y)$. Since Dijkstra's selected $v$ for this iteration, $d'(y) \geq d'(v) = \ell(P_v)$. Combining these inequalities gives $\ell(P) \geq \ell(P') + \ell(x,y) \geq \ell(P_v)$, so the alternative path is at least as long as the path determined by Dijkstra's. $\blacksquare$

Complexity

Consider a graph with $n$ nodes and $m$ edges. Using the while loop in the pseudocode above gives $n-1$ iterations. Computing the minimum edge would take $O(m)$ time, giving an overall time complexity of $O(mn)$.

This can be improved by using a priority queue with key $d'(v)$ for each node $v \in V \setminus S$. Then the ExtractMin method can be used each iteration to get the smallest $d'(v)$. If $v$ is added to $S$ and there is some node $w$ and an edge $e = (v, w)$ then the new key for $w$ is $\min(d'(w), d(v) + \ell_e)$. The ChangeKey operation can then be used to change the key if necessary.

Using a heap based priority queue implementation, both ExtractMin and ChangeKey can be done in $O(\log n)$ time. $O(m)$ time will be needed to populate the priority queue and at most $n$ ExtractMin and $m$ ChangeKey operations will be needed. This results in an overall $O(m\log n)$ time complexity.