Bellman-Ford and Negative Cycles

Dijkstra's algorithm finalises each node's distance the moment it's popped from the queue, and that shortcut breaks the instant an edge has negative weight — a later, cheaper path through a negative edge can undercut a distance that was already declared final. Bellman-Ford gives up that shortcut and, in exchange, handles negative edges correctly, plus it can tell you when the whole question "what's the shortest path" stops making sense.

The idea: relax every edge, V-1 times, no shortcuts

Bellman-Ford does the same relaxation Dijkstra does —

$$\text{dist}[v] \leftarrow \min\big(\text{dist}[v],\ \text{dist}[u] + w(u,v)\big)$$

— but instead of picking edges cleverly via a priority queue, it just relaxes every edge in the graph, in any order, and repeats the whole pass $V - 1$ times. The claim is: after $k$ passes, every shortest path using at most $k$ edges has been found. Since a shortest simple path visits each node at most once, it uses at most $V-1$ edges, so $V-1$ passes are guaranteed enough — no priority queue, no greedy assumption, so negative weights are fine. Cost is $O(VE)$, worse than Dijkstra's $O((V+E)\log V)$, which is the price of dropping the non-negativity requirement.

The bonus: run one more pass, pass $V$. If any distance still improves, some cycle in the graph has negative total weight — a loop you could traverse forever to make the "shortest path" arbitrarily negative, so no finite answer exists. That $V$-th pass is a negative-cycle detector.

Worked example: currency arbitrage

Suppose $1 buys 0.90 EUR, 1 EUR buys 0.80 GBP, and 1 GBP buys 1.45 USD. Multiply the three rates: $0.90 \times 0.80 \times 1.45 = 1.044$. Round-tripping $1 through EUR and GBP returns $1.044 — free money, an arbitrage. Bellman-Ford finds this automatically by weighting each edge $-\log(\text{rate})$: since $\log$ turns products into sums, a profitable loop (product $> 1$) becomes a cycle whose weights sum to a negative number, and the $V$-th relaxation pass will keep finding improvements on it forever, flagging exactly that cycle.

def bellman_ford(edges, n, src):     # edges: list of (u, v, w); O(VE)
    dist = [float("inf")] * n
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:             # V-th pass: negative-cycle check
        if dist[u] + w < dist[v]:
            return None               # negative cycle reachable from src
    return dist

Where it shows up

Interview framing: "cheapest flights within k stops" bounds the number of relaxation passes to $k+1$, which is Bellman-Ford with an early stop. On a desk, triangular and multi-leg FX arbitrage detection is the canonical application; the same negative-cycle idea generalises to any market where implied round-trip pricing (funding rates, cross-listed securities, calendar spreads) should multiply to 1 but occasionally doesn't.