Summary - Bellman-Ford

Run Bellman-Ford and print distances in a mini task.

Summary - Bellman-Ford

In this group you learned Bellman-Ford, which supports negative weights. Edge list, edge loop and negative cycle check combine into the solution.

Now you will write a check function that brings all pieces together. This summary unites the group's concepts in a single piece of code.

Exercise has_negative_cycle function

Write has_negative_cycle(edges, n, src). Run Bellman-Ford, do one extra pass and return True if any edge still relaxes. Print True with print(has_negative_cycle([(0, 1, 1), (1, 2, -1), (2, 0, -1)], 3, 0)).

Show example solution

def has_negative_cycle(edges, n, src):
    # Check if a negative cycle exists
    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
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True
    return False
print(has_negative_cycle([(0, 1, 1), (1, 2, -1), (2, 0, -1)], 3, 0))

Test yourself

When is Bellman-Ford's output valid?
- No negative edges
- Graph undirected
- All edges positive
- No negative cycle
Show answer

No negative cycle — The output is valid if no negative cycle exists.

Negative cycle condition

if dist[u] + w ____ dist[v]: return True

Show answer

if dist[u] + w < dist[v]: return True

Summary - Bellman-Ford: match the terms

init_edges

Edges
relax

Relaxation
bellman_ford

Algorithm
n-1

Passes

Next lesson: Minimum spanning tree

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies