Bellman-Ford: Shortest Paths With Negative Edges and Cycle Detection

Dijkstra's algorithm breaks when an edge weight is negative, because it finalises a node before a cheaper path through a negative edge is found. Bellman-Ford is slower but handles negative weights and tells you when shortest paths don't exist at all.

The algorithm

A shortest simple path has at most V − 1 edges. Relax every edge V − 1 times; after round i, every shortest path using at most i edges is correct.

def bellman_ford(n, edges, src):
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                      # early exit
    for u, v, w in edges:              # one more pass
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None                # negative cycle reachable
    return dist

Negative cycle detection

If any edge still relaxes after V − 1 rounds, a reachable negative cycle exists, so "shortest" is undefined. A classic application is currency arbitrage: use weights -log(rate), and a negative cycle means a profitable loop.

The k-stops variant

"Cheapest flight with at most k stops" is Bellman-Ford limited to k + 1 rounds. The catch: copy the distance array each round and relax from the copy, or a single round can chain multiple edges and violate the stop limit.

for _ in range(k + 1):
    nxt = dist[:]
    for u, v, w in flights:
        if dist[u] + w < nxt[v]:
            nxt[v] = dist[u] + w
    dist = nxt

Complexity and alternatives

• Bellman-Ford: O(V·E) time, O(V) space.
• SPFA (queue-based) is often faster in practice but has the same worst case.
• Dijkstra: O((V + E) log V), non-negative weights only.
• Johnson's algorithm: one Bellman-Ford pass to reweight edges, then Dijkstra from every node for all-pairs shortest paths on sparse graphs with negative edges.

Interview framing: "Weights can be negative, so Dijkstra is out; Bellman-Ford relaxes all edges V − 1 times and an extra pass detects negative cycles."

Disclosure: written by the linkjob.ai team. Free to use for study.