= Solution
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$,
$$
u_{14}^{(2)}=0,\qquad u_{13}^{(2)}=-1,\qquad u_{34}^{(2)}=-1.
$$
The recurrence would give $-2$, by concatenating $1\to2\to3$ and $3\to2\to4$. 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\to2\to4$. Thus
$$
\boxed{u_{14}^{(3)}=0>-2,}
$$
a strict inequality in part (a).
Back to article page
