Visualizer CodeViz · Algorithms, visualized

Part II · Shortest paths · week 4

Bellman–Ford

Relax every edge, V−1 times. Slower than Dijkstra, but it handles negative weights and reports a negative cycle instead of lying about it.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

timeO(V · E)
negative weightssupported
negative cycledetected
after pass kcorrect for ≤ k edges

Reference: Sedgewick & Wayne, §4.4; Bellman 1958, Ford 1956.

Bellman–Ford in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class BellmanFordSP:
    # INVARIANT: after pass k, dist_to[] is correct for every shortest path
    # that uses at most k edges. A shortest path uses at most V-1 edges,
    # so V-1 passes settle everything -- unless a NEGATIVE CYCLE lets a
    # path keep improving forever, which pass V then reveals.

    def __init__(self, digraph, s):
        self.dist_to = [float('inf')] * digraph.V
        self.edge_to = [None] * digraph.V
        self.dist_to[s] = 0.0
        self.has_negative_cycle = False
        for i in range(digraph.V):
            changed = False
            for v in range(digraph.V):    # relax EVERY edge, every pass
                for w, weight in digraph.adj(v):
                    if self.dist_to[v] + weight < self.dist_to[w]:
                        self.dist_to[w] = self.dist_to[v] + weight
                        self.edge_to[w] = v
                        changed = True
            if not changed:
                return                    # a quiet pass means we are done
            if i == digraph.V - 1:
                self.has_negative_cycle = True

Why it works

The invariant is a dynamic program

After pass k, dist_to[] is correct for every shortest path using at most k edges. Pass k+1 extends each of those by one edge. Since a simple shortest path can use at most V−1 edges, V−1 passes are enough — no clever ordering required, which is exactly why it tolerates negative weights.

Detecting a negative cycle

If pass V still improves something, some path is using ≥ V edges, which means it repeats a vertex — a cycle whose total weight is negative. With such a cycle “shortest path” is undefined (go round again, get cheaper), so the honest answer is to report it. Dijkstra in that situation returns a wrong answer with no warning.

The early exit matters

If a whole pass changes nothing, no later pass can change anything either — so return. On the default input that fires long before V−1 passes. The queue-based variant goes further: only vertices whose distance actually changed can produce new improvements, so keep them on a FIFO queue and relax only their edges. That is the version worth implementing (O(E · V) worst case, near-linear in practice), and it is what the course's BellmanFordSP does.

Arbitrage

Take currencies as vertices and exchange rates as edges weighted −ln(rate). A negative cycle is then a sequence of trades that multiplies to more than 1 — an arbitrage opportunity. Turning multiplication into addition with a logarithm so that a shortest-path algorithm applies is one of the most elegant reductions in the course.

What to try in the animation

Negative weights are written the obvious way: 3-4:-1. The negative cycle preset makes the algorithm report failure rather than return nonsense.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Bellman–Ford in the player →

The rest of Shortest paths