Past exam of the Probability, statistics and options II course of the University of Oxford / 2007 / S / 3 / a / 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,\dots ,k-1\}$. Their lengths are at least the respective two minima. In either case,For identical endpoints use the usual empty path of length zero.