= Solution
Use a triangle with vertices $v,a,b$ and weights $w(va)=w(vb)=2$, $w(ab)=-1$. The unique shortest $va$-path is $v,b,a$, of weight one, while the unique shortest $vb$-path is $v,a,b$, also of weight one. A shortest-path tree would therefore need all three edges of the triangle. This is impossible for a tree.
Thus \b[negative edge weights can prevent a <shortest-path tree>], even though the shortest simple path to each individual vertex exists. This is the example in <signed edge weights can prevent a shortest-path tree>.
Back to article page
