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
- Dijkstra's algorithm — An algorithm that finds the cheapest paths from one vertex to all others in a graph whose edge weights are never negative, using a min-heap.
- Bellman-Ford algorithm — A shortest-path algorithm that works even with negative edge weights by relaxing every edge V minus one times.
Taught in
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers