= Signed edge weights can prevent a shortest-path tree
In a triangle with root $v$, assign $w(va)=w(vb)=2$ and $w(ab)=-1$. Among <graph paths>, the unique <shortest path> from $v$ to $a$ is $v,b,a$, and that from $v$ to $b$ is $v,a,b$, both of weight one. A <shortest-path tree> would have to contain all three edges, impossible for a <tree>. The example uses shortest simple paths; arbitrary walks can have unboundedly negative weight by repeatedly traversing the negative edge.
Back to article page
