Advanced · Module 17 · Lesson 2 of 4
Negative edges and Bellman-Ford
When some weights are negative, Dijkstra's settled distances can be wrong. Bellman-Ford relaxes every edge V − 1 times instead, handles negative weights, and detects negative cycles, at a cost of O(V × E).
By the end you can
- Explain why negative weights break Dijkstra's algorithm
- Run Bellman-Ford and explain why V − 1 rounds of relaxation suffice
- Detect negative cycles, and use the round structure for shortest paths with at most k edges
Builds on Dijkstra's algorithm.
01 · A question first
Exchange rates form a graph: dollars to euros, euros to yen, yen back to dollars. If converting around a loop returns more money than you started with, there is free money. Taking logarithms turns that loop into a cycle of negative total weight, which Dijkstra can't see. What can?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- When weights go negative
- Bellman-Ford
- Detecting negative cycles
- Shortest paths with at most k edges
- A distributed version
- Choosing between them
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Something wrong with this lesson? Report a problem