= 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),
$$
\boxed{u_{ij}^{(k)}=\min\{u_{ij}^{(k-1)},u_{ik}^{(k-1)}+u_{kj}^{(k-1)}\}.}
$$
Back to article page
