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!