The pseudocode for Dijkstra's Algorithm in the Graph Traversal activities and in HW4 describes a specific implementation using an updatable min-priority queue. However, Dijkstra's Algorithm may be understood and described in a more general, conceptual way, without reference to particular ADTs. Here's one such description. Each line in the loop is annotated with a letter, corresponding to a note below the pseudocode.
Dijkstra's Algorithm, in the abstract
Given: graph $G = (V, E)$; edge weights $w: E \rightarrow \mathbb{R}^{\ge 0}$; and source vertex $s \in V$.
- Let $D[u] = +∞$ for all $u \in V$; $D[s] = 0$.
- While not all $D[u]$ are finite:
- Consider the set $U = \{v \in V : D[v] = +∞\}$.
- Define, for all $v \in U$, the value $d'(v) = \min_{u : (u,v) \in E} \left( D[u] + w(u,v) \right)$.
- Let $a = \text{argmin}_{v \in U} \left( d'(v) \right)$.
- If $d'(a) = +∞$, then return $D$.
- Otherwise, let $D[a] = d'(a)$.
- $U$ is the set of unknown-distance nodes. If you read the snippet of math “$U = \{v \in V : D[v] = +∞\}$” aloud, you would say: “$U$ is the set of all vertices $v$ where $D[v]$ is $+∞$”.
- The minimum is taken over all nodes $u$ where the edge $(u,v)$ exists: that is, all nodes that have an edge pointing from them to $v$. For each such node $u$, we compute an estimate of the distance to $v$, by going through $u$ and then continuing along the edge $(u, v)$. So $d'(v)$ is our best current estimate, based on the known distances in $D$, of the distance from $s$ to $v$.
- While “min” gives us the minimum value that a function or expression takes on, “argmin” gives us the argument to that function that minimizes it. So $a$ is the node, among all those with unknown distances, whose current best estimate is the least.
- If $d'(a) = +∞$, then that means that $d'(v) = +∞$ for all $v \in U$. So that means that no vertex in $U$ is adjacent to a vertex with a finite value in $D$; otherwise its $d'$ value would be finite. In other words, we've explored all of $s$'s connected component, and the algorithm is finished.
- The node ($a$) with the least estimated distance ($d'(a)$) is surely that distance away from $s$. This is because any other path that could end at $a$ must first pass through some other node in $U$, and there are no shorter paths to get even that far! Since all edge weights are non-negative, the total length of the path from $s$ to some intermediate node to in $U$, and then continuing on to $a$, could not possibly be less than the length of the path from $s$ to that node.