Negative cycle
- Algorithms course
- Advanced
- Lesson 35/56
- 4 min
Detect negative cycles.
Negative cycle
After n-1 passes, one more pass is made. If any edge can still relax, the graph has a negative cycle and the shortest path is undefined.
This check makes the algorithm safe to use. If a negative cycle exists, the user is warned.
Final solution
After n-1 passes, the dist array contains the single-source shortest distances. If no negative cycle, these values are final.
The output has the same form as Dijkstra's: a distance array. The difference is that it also handles negative edges.
Practice bellman_ford function
Write bellman_ford(edges, n, src). Relax all edges n-1 times. Print [0, 3, 1, 4] with print(bellman_ford(init_edges(), 4, 0)).
Starter code
def init_edges():
# Return edge list
return [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]
def bellman_ford(edges, n, src):
# Find single-source shortest pathsSample solution
def init_edges():
# Return edge list
return [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]
def bellman_ford(edges, n, src):
# Find single-source shortest paths
dist = [float('inf')] * n
dist[src] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return dist
print(bellman_ford(init_edges(), 4, 0))Expected output
[0, 3, 1, 4]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Negative cycle: match the terms
| Term | Meaning |
|---|---|
n-1 |
Passes |
1 |
Check pass |
negative cycle |
Undefined |
relaxation |
Update |
2 What is the shortest distance from 0 to 3?
- 3
- 5
- 4 Correct answer
- 1
Explanation: Path 0→2→1→3 gives 1+2+1=4.
3 Loop variable
for u, v, w in ____:for u, v, w in edges:Explanation: edges is right.