= Solution
Use source $1$, as in the preceding part. The <Dijkstra algorithm> extracts vertices in the order \b[$1,3,4,2$]. Distances after relaxing the outgoing <edges> of each extracted vertex are
$$
\begin{array}{c|rrrr}
\text{extracted vertex}&d[1]&d[2]&d[3]&d[4]\\\hline
\text{initial}&0&\infty&\infty&\infty\\
1&0&6&2&\infty\\
3&0&5&2&3\\
4&0&4&2&3\\
2&0&4&2&3
\end{array}
$$
The <shortest path> to $2$ is $1\to3\to4\to2$, with weight $2+1+1=4$; the direct route to $2$ and the route via $3\to2$ are both heavier.
Back to article page
