Bellman–Ford Algorithm

Dijkstra is fast but has one hard rule: no negative edge weights. When your graph has them — a currency exchange where some trades gain value, a routing metric that can be a credit rather than a cost — Bellman–Ford is the algorithm. It’s slower, but it’s correct with negative edges, and it can do something Dijkstra can’t: detect negative cycles.

Why negative edges break Dijkstra

Dijkstra’s correctness rests on a greedy promise: the closest unfinalized node can never be improved later. A negative edge shatters that promise — a path that looks long now can become cheaper after traversing a negative edge, so a node Dijkstra “finalized” might actually have a shorter route it already ruled out.

The idea: relax everything, repeatedly

Bellman–Ford gives up on clever ordering. Instead it relaxes every edge in the graph, and repeats that $V-1$ times. Brute force, but bulletproof.

Why $V-1$ rounds? A shortest path in a graph with $V$ nodes visits at most $V$ nodes, so it uses at most $V-1$ edges. Each full pass over all edges is guaranteed to extend every correct shortest path by at least one more edge (the right relaxation happens somewhere in the pass). After $V-1$ passes, even the longest possible shortest path is fully resolved.

BellmanFord(graph, source):
    dist[source] ← 0
    dist[v] ← ∞ for every other v
    parent[v] ← none

    repeat V - 1 times:                    # ---- V-1 relaxation rounds ----
        for each edge (u → v) with weight w:
            if dist[u] + w < dist[v]:
                dist[v] ← dist[u] + w
                parent[v] ← u

    for each edge (u → v) with weight w:   # ---- one extra round ----
        if dist[u] + w < dist[v]:
            report "negative cycle reachable"
    return dist, parent

Detecting negative cycles

Here’s the payoff. If, after the $V-1$ rounds, you can still relax some edge in one more pass, then a shortest path is being improved by taking more than $V-1$ edges — which is only possible if there’s a negative-weight cycle the path can loop through to keep lowering its cost without bound.

This isn’t a bug to work around; it’s a feature. The classic application is currency arbitrage: model each currency as a node and each exchange rate as an edge weighted by $-\log(\text{rate})$. A negative cycle then corresponds to a sequence of trades that returns you to the starting currency with more money than you began — free profit, detected automatically.

Worked trace (the negative-edge graph above)

Edges: S→A (1), S→B (2), A→B (−2). Three nodes, so $V-1 = 2$ rounds.

After	dist[S]	dist[A]	dist[B]
init	0	∞	∞
round 1	0	1	−1
round 2	0	1	−1

Round 1 relaxes S→A (A = 1), S→B (B = 2), then A→B (B = $1 + (-2) = -1$, beating 2). Round 2 changes nothing → stable. Final: B = −1 via S → A → B, the answer Dijkstra would have missed. A final check pass also changes nothing, so there’s no negative cycle here.

Complexity

$V-1$ rounds, each scanning all $E$ edges:

$$O(V \cdot E) \text{ time}, \qquad O(V) \text{ space}$$

That’s much slower than Dijkstra’s $O((V+E)\log V)$ — the price of handling negative weights. On a graph with 10,000 nodes and 100,000 edges, that’s a billion operations versus a few million. Use Bellman–Ford only when you must.

• SPFA (Shortest Path Faster Algorithm) is a queue-based optimization that’s often much faster in practice, though its worst case is the same.
• Johnson’s algorithm cleverly runs Bellman–Ford once to reweight all edges to be non-negative, then Dijkstra from every node — the efficient way to get all-pairs shortest paths on a graph that has negative edges but no negative cycles.

When to use it

• You have negative edge weights and Dijkstra is off the table.
• You need to detect negative cycles — arbitrage, feasibility of difference-constraint systems, “profit loop” checks.
• Distributed routing — the distance-vector protocols behind early internet routing (RIP) are essentially Bellman–Ford run across routers.
• Otherwise prefer Dijkstra — if all weights are non-negative, the $O(VE)$ cost is simply wasted.