Bellman-Ford & Negative Edges
Handle negatives and detect cycles.
Bellman-Ford & Negative Edges is a free Coding Interview Prep lesson on CoddyKit. This is lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, and your progress syncs across the web and the CoddyKit app. The Coding Interview Prep course includes 4 lessons in total.
When Dijkstra Fails
Dijkstra trusts that a popped distance is final, but a negative edge can later make a path cheaper. So it breaks.
Enter Bellman-Ford
Bellman-Ford handles negative edge weights. It is slower than Dijkstra but robust where greedy logic cannot be trusted.
The Core Operation
It repeatedly relaxes every edge: if dist[u] plus the edge weight beats dist[v], update dist[v] to that smaller value.
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wHow Many Rounds
A shortest path uses at most V minus 1 edges, so V-1 rounds of relaxing every edge is enough to settle all distances.
for _ in range(n - 1):
relax_all_edges()Initialize Distances
Start with every distance at infinity except the source at zero, exactly like you do in Dijkstra.
dist = [float('inf')] * n
dist[src] = 0One Full Pass
Each pass walks the entire edge list once and relaxes each edge. Improvements ripple outward one hop per pass.
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wWhy V-1 Suffices
After k passes, all shortest paths using k edges are correct. By V-1 passes, every simple shortest path is finished.
The Extra Pass
Run one more pass. If any distance still drops, something keeps getting cheaper, which signals a negative cycle.
Detecting Negative Cycles
A negative cycle means no finite shortest path exists, since you can loop forever to lower the cost without bound.
for u, v, w in edges:
if dist[u] + w < dist[v]:
return 'negative cycle'The Running Time
You relax E edges across V passes, so Bellman-Ford runs in O(V * E), fine for small or medium graphs.
Dijkstra or Bellman-Ford
Pick Dijkstra for non-negative weights and speed. Pick Bellman-Ford when negatives appear or you must catch a bad cycle.
Quick Check
After V-1 passes, a distance still decreases on one more pass. What does that mean?
Recap: Bellman-Ford
Relax all edges for V-1 passes, then one more to catch negative cycles. It is O(V*E) but works where Dijkstra cannot. ✅
Learn Coding Interview Prep with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 90
- Lessons
- 360
Frequently Asked Questions
Is the “Bellman-Ford & Negative Edges” lesson free?
Yes — the full text of “Bellman-Ford & Negative Edges” is free to read here on the web. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO. The Coding Interview Prep course includes 4 lessons in total.
What will I learn in “Bellman-Ford & Negative Edges”?
Handle negatives and detect cycles. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners, so you can start here or from the beginning and move at your own pace. This is lesson 3 of 4.
How long does the “Bellman-Ford & Negative Edges” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Dijkstra with a Heap
- 0-1 BFS with a Deque
- Bellman-Ford & Negative Edges
- Floyd-Warshall All-Pairs