Past exam of the Probability, statistics and options II course of the University of Oxford / 2007 / S / 3 / b / Solution

An old shortest graph path is still allowed at stage $k$, so $u_{ij}^{(k)}\le u_{ij}^{(k-1)}$. Concatenating shortest $i$--$k$ and $k$--$j$ paths gives a walk of length $u_{ik}^{(k-1)}+u_{kj}^{(k-1)}$, but it may repeat vertices. Every repeated section is a closed walk. In the absence of negative-length cycles in a graph, each such closed walk has nonnegative length: decompose it into simple cycles. Removing these sections therefore produces an allowed simple graph path of no greater length. This proves the other upper bound. Together with part (a),