Bellman-Ford Shortest Paths

An algorithm that finds shortest paths in graphs with negative edge weights and detects negative cycles as well.

Dijkstra's algorithm cannot find shortest paths reliably when a weighted graph has negative edge weights. Bellman-Ford permits negative weights and finds shortest paths. It also detects negative cycles.

What it solves

Bellman-Ford finds the shortest path from a single source vertex to every other vertex. Unlike Dijkstra, it works when some edge weights are negative.

Key properties

• It works on graphs containing negative weights.
• It detects negative cycles that the source can reach.
• Its time complexity is $O(V \times E)$, where V is the vertex count and E is the edge count.

Dijkstra vs Bellman-Ford

The algorithm

Relaxation (Step 1)

Iterate over every edge V-1 times and update the distances.

Relaxation updates a recorded distance when the algorithm finds a shorter path to that vertex.

for i in range(V-1):
    for (u, v, w) in edges:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

Why V-1 iterations: a shortest path contains at most V-1 edges.

Negative Cycle Detection (Step 2)

After the V-1 iterations, scan the edges one more time. If any distance still updates, a negative cycle exists.

for (u, v, w) in edges:
    if dist[u] + w < dist[v]:
        return "negative cycle detected"

Example graph

Trace

• Initial: [0, ∞, ∞, ∞, ∞]
• After pass 1: [0, 2, 7, 4, 2]
• After pass 2: [0, 2, 7, 4, -2]
• After pass 3: [0, 2, 7, 4, -2]

Result: [0, 2, 7, 4, -2]

The intermediate values per pass come from relaxing in the edges order below. A different edge order can produce different intermediate values. The final result is the same.

Python implementation

bellman_ford(start, n, edges) takes the source vertex start, the vertex count n, and the edge list edges. It initializes the distance array to INF and sets the source distance to 0. It returns a (dist, has_negative_cycle) tuple. When has_negative_cycle is True, the distance array is unreliable.

import sys
 
def bellman_ford(start, n, edges):
    INF = sys.maxsize
    dist = [INF] * n
    dist[start] = 0
 
    # V-1 iterations
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
 
    # negative cycle detection
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return dist, True  # negative cycle exists
 
    return dist, False
 
 
# Run
edges = [
    (0, 1, 6), (0, 2, 7), (1, 2, 8), (1, 3, 5),
    (1, 4, -4), (2, 3, -3), (2, 4, 9),
    (3, 1, -2), (4, 0, 2), (4, 3, 7)
]
 
dist, has_negative_cycle = bellman_ford(0, 5, edges)
 
if has_negative_cycle:
    print("Negative cycle detected")
else:
    print(f"Shortest distances: {dist}")

Java implementation

The logic matches the Python version. When it detects a negative cycle, it throws an exception instead of returning a boolean.

import java.util.*;
 
public class BellmanFord {
    static class Edge {
        int u, v, w;
        Edge(int u, int v, int w) {
            this.u = u; this.v = v; this.w = w;
        }
    }
 
    public static int[] bellmanFord(int start, int n, List<Edge> edges) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
 
        // V-1 iterations
        for (int i = 0; i < n - 1; i++) {
            for (Edge e : edges) {
                if (dist[e.u] != Integer.MAX_VALUE &&
                    dist[e.u] + e.w < dist[e.v]) {
                    dist[e.v] = dist[e.u] + e.w;
                }
            }
        }
 
        // negative cycle detection
        for (Edge e : edges) {
            if (dist[e.u] != Integer.MAX_VALUE &&
                dist[e.u] + e.w < dist[e.v]) {
                throw new RuntimeException("Negative cycle detected");
            }
        }
 
        return dist;
    }
}

Go implementation

Like the Python version it returns (dist, bool), using math.MaxInt32 in place of infinity.

func BellmanFord(start, n int, edges []Edge) ([]int, bool) {
    dist := make([]int, n)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[start] = 0
 
    // V-1 iterations
    for i := 0; i < n-1; i++ {
        for _, e := range edges {
            if dist[e.u] != math.MaxInt32 &&
               dist[e.u]+e.w < dist[e.v] {
                dist[e.v] = dist[e.u] + e.w
            }
        }
    }
 
    // negative cycle detection
    for _, e := range edges {
        if dist[e.u] != math.MaxInt32 &&
           dist[e.u]+e.w < dist[e.v] {
            return dist, true
        }
    }
 
    return dist, false
}

When a negative cycle exists

The shortest distance is undefined for a vertex reachable through a negative cycle that the source can reach. Repeating that cycle keeps lowering the path cost toward $-\infty$.

flowchart LR
    S["Source S"] --> A["Negative-cycle vertex A"]
    A --> B["Negative-cycle vertex B"]
    B --> A
    B --> D["Affected vertex D"]
    X["Unreachable X"] --> Y["Unreachable negative cycle Y"]
    Y --> X

The distances to A, B, and D are unreliable. The unreachable cycle through X and Y does not affect this single-source result. The implementation checks source reachability with dist[u] != INF. It rejects the complete distance array when it finds a reachable negative cycle.

Applications

Summary

• V-1 passes to relax distances
• One extra pass to decide whether a negative cycle exists
• Time complexity $O(V \times E)$, which is inefficient on large graphs
• The default choice whenever negative weights are involved

Bellman-Ford settles shortest distances in V-1 relaxation passes and identifies a reachable negative cycle with one additional check. Distances are undefined for vertices reachable from such a cycle.

This implementation rejects the entire distance array when it detects that condition. Its $O(V \times E)$ complexity makes it suitable when negative weights or negative-cycle detection justify the extra work.