 Solution

ID: 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,

u_{ij}^{(k)} \geq min {u_{ij}^{(k - 1)}, u_{ik}^{(k - 1)} + u_{kj}^{(k - 1)}} .

For identical endpoints use the usual empty path of length zero.

 New to topics? Read the docs here!