Signed edge weights can prevent a shortest-path tree
ID: signed-edge-weights-can-prevent-a-shortest-path-tree
In a triangle with root , assign and . Among graph paths, the unique shortest path from to is , and that from to is , 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.
New to topics? Read the docs here!