Bellman-Ford & Negative Edges
Handle negatives and detect cycles.
Bellman-Ford & Negative Edges is a free Coding Interview Prep lesson on CoddyKit — 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, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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. ✅
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, and the Coding Interview Prep course includes 4 lessons in total. 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.
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; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
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