negative edge weight

An edge whose weight is below zero, as when taking a route earns a refund or credit rather than costing something.

In more detail

Dijkstra's greedy step assumes that a path can only get more expensive as it grows, which a negative edge breaks: a vertex already declared final might have a cheaper route through it. Bellman-Ford handles negative weights, and can also detect a negative cycle, where no shortest path exists.

Related terms

Taught in

References