Bellman-Ford Algorithm — Shortest Paths with Negative Weights

Financial trading systems use graph algorithms to find arbitrage opportunities — sequences of currency exchanges that yield profit. GPS routing engines handle toll roads, ferry routes, and restricted zones. Network packet routing protocols like RIP (Routing Information Protocol) propagate cost updates across distributed nodes. In every one of these systems, the edge weights on a graph can be negative. That single reality invalidates Dijkstra's algorithm entirely, and it's the reason Bellman-Ford exists.

The core problem Bellman-Ford solves is single-source shortest paths in a weighted directed graph where edge weights can be negative. Dijkstra's greedy approach assumes that once a node is 'settled' its shortest distance is final — a guarantee that collapses the moment a future negative edge could have produced a cheaper path. Bellman-Ford abandons the greedy assumption and instead performs exhaustive relaxation: it checks every edge, repeatedly, until it's mathematically certain no cheaper path exists. As a bonus, it can detect negative-weight cycles — loops in the graph where traversing the cycle keeps reducing your total cost to negative infinity, making shortest paths undefined.

By the end of this article you'll understand exactly why Bellman-Ford performs V-1 relaxation passes and not V or V-2, how to implement it correctly in Java with proper negative-cycle detection, where it outperforms Dijkstra in practice, what the subtle off-by-one bugs look like in interview code, and how production systems like distributed routing protocols derive their design directly from this algorithm's properties.

What is Bellman-Ford? — Plain English

Bellman-Ford finds the shortest path from a source node to all other nodes in a weighted graph, even when some edge weights are negative. Dijkstra's algorithm fails with negative edges because it assumes that once a node is finalized, its distance cannot improve — negative edges can always make a path shorter. Bellman-Ford handles this by relaxing all edges V-1 times. Why V-1? The shortest path between any two nodes in a graph with V nodes uses at most V-1 edges (otherwise it would visit a node twice, forming a cycle). After V-1 relaxation passes, all shortest paths are found. A V-th pass that still relaxes an edge signals a negative cycle — a loop whose total weight is negative, making the shortest path undefined.

How Bellman-Ford Works — Step by Step

Algorithm on a graph with V vertices and E edges:

1. Initialize dist[source] = 0, dist[all others] = infinity.
2. Repeat V-1 times:
3. a. For each edge (u, v, weight) in the edge list:
4. b. If dist[u] + weight < dist[v]: relax → dist[v] = dist[u] + weight.
5. Negative cycle detection: do one more pass over all edges.
6. a. If any edge (u,v,w) still satisfies dist[u] + w < dist[v], a negative cycle exists.
7. Return the dist array (and predecessors if path reconstruction is needed).

Worked Example — 5-Node Graph with Negative Edge

Graph edges (u,v,weight): (0,1,4),(0,2,5),(1,2,-3),(1,3,6),(2,4,2),(3,4,1),(4,3,-2). Source=0.

Initial: dist=[0,inf,inf,inf,inf].

Passes 3,4: no changes. Final dist=[0,4,1,1,3].

Implementation

Bellman-Ford iterates over the edge list V-1 times, relaxing each edge. The edge list representation (list of (u,v,weight) tuples) is simpler to use than adjacency lists for this algorithm. The V-th pass detects negative cycles. Time complexity O(VE) makes it slower than Dijkstra's O((V+E) log V), but it handles negative weights. Space complexity is O(V) for the distance array plus O(E) for the edge list.

def bellman_ford(num_vertices, edges, source):
    """
    edges: list of (u, v, weight)
    Returns (dist, has_negative_cycle)
    """
    INF = float('inf')
    dist = [INF] * num_vertices
    dist[source] = 0

    # Relax all edges V-1 times
    for _ in range(num_vertices - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:  # Early exit if no relaxation occurred
            break

    # Detect negative cycles (V-th pass)
    has_neg_cycle = False
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            has_neg_cycle = True
            break

    return dist, has_neg_cycle

# Example: 4-node graph
edges = [(0,1,4),(0,2,5),(1,2,-3),(1,3,6),(2,3,2)]
dist, neg = bellman_ford(4, edges, 0)
print(dist)   # [0, 4, 1, 3]
print(neg)    # False

Frequently Asked Questions