What is the Bellman-Ford algorithm?

Bellman-Ford computes the shortest path from a single source node to every other node in a weighted, directed graph — and unlike Dijkstra's algorithm it works even when some edges have negative weights. It repeatedly relaxes every edge V-1 times (where V is the number of nodes) until the distances settle, and can also report whether the graph contains a negative-weight cycle.

Why does Bellman-Ford relax edges V-1 times?

A shortest path in a graph with V nodes uses at most V-1 edges (any more would repeat a node). Each full pass of relaxing all edges guarantees that shortest paths using one more edge become correct, so after V-1 passes every shortest path — which has at most V-1 edges — is fully computed.

How does Bellman-Ford detect a negative cycle?

After V-1 passes the distances should be final. Bellman-Ford does one more pass over all edges: if any edge can still be relaxed (dist[u] + w < dist[v] is still true), then a shorter path keeps appearing, which is only possible if a negative-weight cycle is reachable. That extra pass is the negative-cycle test.

Bellman-Ford vs Dijkstra — when do you use each?

Dijkstra is faster — O((V+E) log V) — but assumes all edge weights are non-negative; a negative edge can break its greedy assumption. Bellman-Ford is slower — O(V·E) — but handles negative weights and detects negative cycles. Use Dijkstra when weights are non-negative and speed matters; use Bellman-Ford when negatives are possible.

ALGORITHMS · 13 / BELLMAN-FORD

The Patient Router.

Dijkstra is fast but proud — one negative edge and it's wrong. Bellman-Ford is patient: it relaxes every edge again and again until the numbers stop moving, so it finds the shortest paths even with negative weights — and spots a negative cycle when one exists.

THE GIST · 20 SECONDS

Bellman-Ford finds shortest paths from one source. Start every distance at ∞ (source = 0), then relax every edge — if dist[u]+w < dist[v], lower dist[v] — and repeat the whole sweep V − 1 times. After that the distances are final. One extra pass that still improves anything means a negative cycle. Slower than Dijkstra, but it survives negatives.

Relaxtry a shorter route to v
Sourcewhere distance = 0
V − 1 passeslongest path has V−1 edges
Neg cyclestill improving = trap

Hit Step to relax the next edge — or Play and watch the distances ripple out from the source and settle.

UNDER THE HOOD

What you just played, written down

One operation — relax — repeated until nothing changes. No priority queue, no assumptions about signs. Just patience, and a clever bound on how many passes you need.

How Bellman-Ford thinks — four moves

Seed the distances. dist[source] = 0, everyone else ∞. We only know we can stay put for free.
Relax every edge. For each (u, v, w): if dist[u] + w < dist[v], we found a shorter way — lower dist[v].
Repeat V − 1 times. A shortest path has at most V − 1 edges, so V − 1 full sweeps lock in every one.
One more pass = the alarm. If any edge still relaxes, distances never settle — a negative cycle is reachable.

WHY DIJKSTRA CAN'T DO THIS

Dijkstra commits a node's distance the moment it's popped, betting no later path is cheaper. A negative edge can make a later path cheaper, breaking that bet. Bellman-Ford commits to nothing until V − 1 passes are done.

The whole thing in code

def bellman_ford(n, edges, src):   # edges: [u, v, w]
    dist = [float('inf')] * n
    dist[src] = 0
    # relax every edge V-1 times
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # one more pass: still improving = negative cycle
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None            # negative cycle!
    return dist

TIMEO(V·E)V−1 passes × E edges

SPACEO(V)one distance per node

IT'S DYNAMIC PROGRAMMING

Pass k computes the shortest path using at most k edges. Each pass builds on the last — the same "solve by edge count" recurrence you'd write as a DP table, run in place over the distance array.

⚠ Negative cycle = no answer

If a reachable cycle has negative total weight, you can loop it forever to make paths shorter without bound — so "shortest path" is undefined. Bellman-Ford's job there is to detect it, not to return a distance.

↔ Early exit & SPFA

If a full pass changes nothing, you can stop early — the distances are final. The SPFA variant only re-relaxes edges out of recently-updated nodes, often much faster in practice.

★ Where it's used

Currency arbitrage (a negative cycle = free money), routing protocols (distance-vector / RIP), and as the first stage of Johnson's all-pairs shortest paths.

SOLVE IT YOURSELF

Solve it: single-source shortest paths

This one is yours to write — in Python or TypeScript, running for real in your browser. Relax every edge V-1 times and return the distances. Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement bellman_ford(n, edges, src): n nodes (0…n-1), directed edges as [u, v, w]. Return the list of shortest distances from src (use a large number / infinity for unreachable). Assume no negative cycle for the returned distances.

HINTS — 4 IDEAS

Init dist = [inf]*n, then dist[src] = 0.
Repeat n-1 times: for every edge (u,v,w), if dist[u]+w < dist[v], set dist[v] = dist[u]+w.
Guard against inf + w: only relax when dist[u] is finite (not infinity).
Return dist — the shortest distance from src to each node.

CPython · WebAssembly

QUICK CHECK

Did it stick?

FAQ

Bellman-Ford, answered

What is Bellman-Ford?

A single-source shortest-path algorithm that works with negative edge weights. It relaxes every edge V − 1 times until the distances settle, and can detect a negative cycle with one extra pass.

What does relaxing an edge mean?

For edge (u, v, w): if dist[u] + w < dist[v], a shorter route to v exists, so set dist[v] = dist[u] + w. That single check, repeated, is the whole algorithm.

Why V − 1 passes?

A shortest path visits each node at most once, so it uses at most V − 1 edges. Each pass finalizes shortest paths of one more edge, so V − 1 passes finalize them all.

How does it detect a negative cycle?

After V − 1 passes the distances should be final. If one more pass still relaxes an edge, distances never converge — a reachable negative-weight cycle exists.

Bellman-Ford vs Dijkstra?

Dijkstra is faster (O((V+E) log V)) but needs non-negative weights. Bellman-Ford is slower (O(V·E)) but handles negatives and detects negative cycles.

▶ Watch it explained

Prefer a video walkthrough?

Finished this one? 0 / 99 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA