Negative cycle

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.

Exercise 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)).

Show example 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))

Test yourself

Negative cycle: match the terms

n-1

Passes
1

Check pass
negative cycle

Undefined
relaxation

Update
What is the shortest distance from 0 to 3?
- 3
- 5
- 4
- 1
Show answer

4 — Path 0→2→1→3 gives 1+2+1=4.

Loop variable

for u, v, w in ____:

Show answer

for u, v, w in edges:

Next lesson: Summary - Bellman-Ford

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies