= Solution
Take a shortest allowed simple <graph path>. If it does not use $k$ as an intermediate <vertex>, its length is at least $u_{ij}^{(k-1)}$. If it does, simplicity makes $k$ occur only once. Splitting there gives an $i$--$k$ path and a $k$--$j$ path whose intermediate <vertices> are in $\{1,\ldots,k-1\}$. Their lengths are at least the respective two minima. In either case,
$$
\boxed{u_{ij}^{(k)}\ge\min\{u_{ij}^{(k-1)},u_{ik}^{(k-1)}+u_{kj}^{(k-1)}\}.}
$$
For identical endpoints use the usual empty path of length zero.
Back to article page
