Dijkstra's Shortest-Path Algorithm

Dijkstra's algorithm computes shortest-path distances from a single source to all other vertices in a weighted graph with nonnegative edge weights. It repeatedly extracts the unsettled vertex with the smallest tentative distance from a min-heap priority queue, then relaxes its outgoing edges. With predecessor pointers, it also reconstructs the actual shortest path.

Step 1 of 157%

Tutorial

The Algorithm

Dijkstra's shortest-path algorithm computes the shortest distance from a source vertex $s$ to every other vertex in a weighted graph with nonnegative edge weights.

The algorithm maintains a tentative distance $d[v]$ for every vertex and a set of settled vertices whose distances are finalized.

Algorithm:

Initialize $d[s] = 0$ and $d[v] = \infty$ for all $v \neq s$ .
While an unsettled vertex remains:
- Extract the unsettled vertex $u$ with the smallest $d[u]$ and mark it settled.
- For each edge $(u, v)$ of weight $w$ , relax: if $d[u] + w < d[v]$ , set $d[v] \leftarrow d[u] + w$ .

The extract-min step is implemented with a min-heap keyed on $d[v]$ , giving $O(\log n)$ per extraction.

Tiny trace. Consider three vertices with edges $A\text{--}B: 4$ , $A\text{--}C: 2$ , $B\text{--}C: 1$ , starting from $A$ :

\begin{align*} \text{Settle } A\ (d=0): &\quad d[B] \leftarrow 4,\ d[C] \leftarrow 2. \\ \text{Settle } C\ (d=2): &\quad d[B] = \min(4,\,2+1) = 3. \\ \text{Settle } B\ (d=3). & \end{align*}

Final distances from $A$ : $d[A]=0,\ d[B]=3,\ d[C]=2$ .