Bellman-Ford Algorithm: Shortest Paths with Negative Weights

The Bellman-Ford algorithm finds single-source shortest paths even when the graph has negative edge weights — something Dijkstra cannot handle. It works by relaxing every edge repeatedly: V - 1 full passes are enough for the shortest paths to settle, and one extra pass detects a negative cycle. It runs in O(V · E) time — slower than Dijkstra, but more general.

Why V - 1 passes

A shortest path in a graph with V vertices uses at most V - 1 edges (any more would repeat a vertex, and on a non-negative cycle that never helps). Each pass over all edges lets correct distances propagate one edge further, so after V - 1 passes every shortest path is found.

#include <vector>
#include <climits>

struct Edge { int u, v, w; };

// returns dist; sets hasNegCycle if a negative cycle is reachable
std::vector<long long> bellmanFord(int V, const std::vector<Edge>& edges,
                                   int src, bool& hasNegCycle) {
    const long long INF = LLONG_MAX;
    std::vector<long long> dist(V, INF);
    dist[src] = 0;
    for (int i = 0; i < V - 1; i++) {              // V-1 relaxation rounds
        for (const auto& e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
                dist[e.v] = dist[e.u] + e.w;
        }
    }
    hasNegCycle = false;                            // extra pass to detect
    for (const auto& e : edges)
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
            hasNegCycle = true;
    return dist;
}

class Edge { int u, v, w; Edge(int u,int v,int w){this.u=u;this.v=v;this.w=w;} }

// returns dist; negCycle[0] set true if a negative cycle is reachable
long[] bellmanFord(int V, List<Edge> edges, int src, boolean[] negCycle) {
    final long INF = Long.MAX_VALUE;
    long[] dist = new long[V];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int i = 0; i < V - 1; i++) {              // V-1 relaxation rounds
        for (Edge e : edges)
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
                dist[e.v] = dist[e.u] + e.w;
    }
    negCycle[0] = false;                            // extra pass to detect
    for (Edge e : edges)
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
            negCycle[0] = true;
    return dist;
}

// edges: array of [u, v, w]; returns { dist, hasNegCycle }
function bellmanFord(V, edges, src) {
  const dist = new Array(V).fill(Infinity);
  dist[src] = 0;
  for (let i = 0; i < V - 1; i++) {               // V-1 relaxation rounds
    for (const [u, v, w] of edges)
      if (dist[u] !== Infinity && dist[u] + w < dist[v])
        dist[v] = dist[u] + w;
  }
  let hasNegCycle = false;                          // extra pass to detect
  for (const [u, v, w] of edges)
    if (dist[u] !== Infinity && dist[u] + w < dist[v])
      hasNegCycle = true;
  return { dist, hasNegCycle };
}

# edges: list of (u, v, w); returns (dist, has_neg_cycle)
def bellman_ford(V, edges, src):
    INF = float('inf')
    dist = [INF] * V
    dist[src] = 0
    for _ in range(V - 1):                          # V-1 relaxation rounds
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    has_neg_cycle = False                           # extra pass to detect
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            has_neg_cycle = True
    return dist, has_neg_cycle

Pitfall: Always guard with dist[u] != INF before relaxing. Adding a finite weight to “infinity” can overflow (in C++/Java) or wrongly relax an unreachable vertex.

Detecting negative cycles

If any edge can still be relaxed after V - 1 passes, a negative cycle is reachable — a loop whose total weight is negative, which makes “shortest path” undefined (you could loop forever to drive the cost down). The extra pass above flags exactly this. To find which vertices are affected, mark every vertex relaxed in that final pass and propagate.

Going deeper: A common optimization stops early if a full pass changes nothing (the distances have converged), often finishing well before V - 1 rounds.

Bellman-Ford vs Dijkstra

                     Bellman-Ford        Dijkstra
Negative weights     yes                 no
Negative-cycle test  yes                 no
Time complexity      O(V*E)              O((V+E) log V)
Best for             negative edges,     non-negative
                     small/medium graphs weights, large graphs

When to use it

Choose Bellman-Ford when edges can be negative (currency arbitrage, certain scheduling/cost models) or when you must detect negative cycles. For non-negative weights, Dijkstra is faster. For all-pairs shortest paths on a dense graph, see Floyd-Warshall.