dijkstra's algorithm

1. inductive step

Let \(F\) be the set of frontier nodes.
Let \(S\) be the set of confirmed nodes.
(1) We take the \(v\) node in \(F\) that has the minimum candidate distance.
Suppose there's another path \(P\) to \(v\) that is shorter. It contains the edge \((v,v')\). \(v'\) cannot be in \(S\), otherwise we could go through \(v'\) to get a shorter candidate distance. But \(P\) must enter \(S\) at some point, because the source is contained in \(S\). That is, \(P\) must contain the edge \((w,u)\) such that \(w\) is on the frontier and \(u\) is confirmed. But the candidate distance to \(w\) must be more than the candidate distance to \(v\) otherwise (1) is violated. Moreoever, that candidate distance to \(w\) must be the true distance, because \(u\) has already been visited, so \((w,u)\) has already been accounted for. But this means that the distance to \(w\) is already longer than the candidate distance to \(v\), not counting the weight from \(w\) to \(v\).