Vibe Engines Learn
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

  1. Seed the distances. dist[source] = 0, everyone else ∞. We only know we can stay put for free.
  2. Relax every edge. For each (u, v, w): if dist[u] + w < dist[v], we found a shorter way — lower dist[v].
  3. Repeat V − 1 times. A shortest path has at most V − 1 edges, so V − 1 full sweeps lock in every one.
  4. 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
  1. Init dist = [inf]*n, then dist[src] = 0.
  2. Repeat n-1 times: for every edge (u,v,w), if dist[u]+w < dist[v], set dist[v] = dist[u]+w.
  3. Guard against inf + w: only relax when dist[u] is finite (not infinity).
  4. 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.

RESULT

—

Next → drop the negative weights and commit each node as you pop it from a priority queue — that's Dijkstra's algorithm, faster but sign-sensitive.

Finished this one? 0 / 17 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

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →