Bellman-Ford algorithm
A shortest-path algorithm that works even with negative edge weights by relaxing every edge V minus one times.
In more detail
After k rounds, every shortest path that uses at most k edges is correct, and no simple path needs more than V minus one edges. It costs O(V × E), slower than Dijkstra's algorithm. If a further round still improves a distance, the graph contains a negative cycle.
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.
- relaxation — Checking whether going through vertex u gives a cheaper route to its neighbour v than the best one known, and updating v's distance if so.
- negative edge weight — An edge whose weight is below zero, as when taking a route earns a refund or credit rather than costing something.
Taught in
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers