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

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.

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),

Initialize an $n\times n$ array $d$ with $d_{ii}=0$ and $d_{ij}=a_{ij}$ for $i\ne j$. For $k=1,\dots ,n$, replace every entry in place byThis is the Floyd-Warshall algorithm. At the start of stage $k$, the induction hypothesis is $d_{ij}=u_{ij}^{(k-1)}$. During that stage, row $k$ and column $k$ do not change: $d_{kk}=0$ and no negative cycle can lower it. Hence the operands $d_{ik},d_{kj}$ remain the stage-start values even with in-place updates. Part (b) proves that after the stage every entry is $u_{ij}^{(k)}$. Induction gives all shortest path lengths after stage $n$. The algorithm uses $n^2$ stored lengths and $O(n^3)$ arithmetic operations, with only a fixed number of loop counters beyond the array.

Use four vertices, with lengths $a_{12}=a_{24}=0$, $a_{23}=a_{32}=-1$, and every other non-loop arc of length $100$. The two arcs between $2$ and $3$ form a negative-length cycle in a graph. For $i=1$, $j=4$, $k=3$,The recurrence would give $-2$, by concatenating $1\to 2\to 3$ and $3\to 2\to 4$. That walk repeats $2$, so it is not a simple graph path. Every simple graph path from $1$ to $4$ still has length at least zero, attained by $1\to 2\to 4$. Thusa strict inequality in part (a).