ZERO / HERO
Rumours spreading one hop per round

Bellman-Ford & Negative Edges

The analogy

Instead of cleverly picking who to visit next, you brute-force it: every round, you look at every road and see whether it improves any known distance. After one round every one-road route is known, after two rounds every two-road route, and so on. Slower, but it copes with roads that somehow give you time back — and it can spot a loop that makes you infinitely early.

Visualizer

Relaxing every edge, round by round

step 1 / 8
dist
A0
B∞
C∞
D∞
E∞

Bellman-Ford does not pick clever vertices. It relaxes EVERY edge, over and over. Note C→B has weight −3 — Dijkstra would be illegal here.edges: A-B 4, A-C 2, C-B -3, B-D 3, C-D 6, D-E 2

def bellman_ford(n, edges, src):
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0

    for _ in range(n - 1):               # V-1 rounds
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                        # early exit

    for u, v, w in edges:                 # one extra round
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle reachable")
    return dist

# O(V * E) — handles negative weights
Check yourself

Why exactly V−1 relaxation rounds?