Bellman-Ford, Hands-On: Shortest Paths with Negative Weights

The Story That Explains Bellman-Ford

Bellman-Ford finds shortest paths from one source to every node in a weighted, directed graph — and unlike Dijkstra, it works even when some edge weights are negative. Its method is brute-force but bulletproof: relax every edge, V−1 times.

Each pass sweeps through every edge again — better distances ripple one hop further each time.

The Three Phases

The Graph We'll Use

Four nodes (A–D), source A, a directed graph with one negative edge (B → C = −2). The edges are processed in the order below — deliberately "awkward" so you can watch distances need several passes to settle.

Hands-On: Watch Each Line Run

The heart of the tutorial. Press Play (or Step) and watch each edge light up amber as it's tested, the target node flash green when its distance improves, and the distance labels fall pass after pass. The edge strip shows progress through the current pass, and the exact Python line running lights up on the right.

def bellman_ford(graph, edges, src):
    dist = {v: float('inf') for v in graph}
    dist[src] = 0
    for i in range(len(graph) - 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]:
            raise ValueError('negative cycle')
    return dist

The Code, Line by Line — "This Line Does That"

Same program as the animation, fully annotated. Each line maps to a job the visualiser highlights.

def bellman_ford(graph, edges, src):
    dist = {v: float('inf') for v in graph}  # all nodes unknown
    dist[src] = 0                          # source is 0 from itself
    for i in range(len(graph) - 1):       # V-1 full passes
        for u, v, w in edges:               # try to relax EVERY edge
            if dist[u] + w < dist[v]:        # found a cheaper path?
                dist[v] = dist[u] + w        # relax: update distance
    for u, v, w in edges:                   # one extra pass = detector
        if dist[u] + w < dist[v]:            # still improving?
            raise ValueError('negative cycle')  # no shortest path
    return dist                            # shortest distance to each node

Full Working — Every Edge, Every Pass

Here is the complete trace from source A. Watch how node D needs all three passes to reach its true value (14 → 8 → 5), because its shortest path A→B→C→D has three edges — one resolved per pass. skip (∞) means the source end was still unknown.

Detecting a Negative Cycle

A negative cycle is a loop whose edge weights sum to less than zero. Going around it keeps lowering the total forever, so no shortest path exists. After V−1 passes distances should be final — if a V-th pass still improves something, a negative cycle is present.

X→Y→Z→X sums to 1 + (−3) + 1 = −1 < 0 — a negative cycle.

Bellman-Ford vs Dijkstra

Time & Space Complexity

Benefits

When To Use It — and When Not To

Where Bellman-Ford Sits Among Path Algorithms

Golden Rules