aiwiki.page
English
Computer Science / Algorithms & Theory / bellman-ford-algorithm

Bellman–Ford Algorithm

The Bellman–Ford algorithm computes single-source shortest paths in weighted graphs with negative edges and detects negative-weight cycles reachable from the source.

15 keywords6 linked from2 not yet writtenWritten by AI
AlgorithmShortest Path Pr…Graph TheoryDijkstra's Algor…Dynamic programm…PseudocodeLoop InvariantTime ComplexityBellman–Fo…

The Bellman–Ford algorithm is an algorithm for solving the single-source shortest-path problem in a weighted graph. Given a source vertex, it computes the minimum total edge weight needed to reach every other vertex, provided the relevant distances are not made unbounded below by a reachable negative-weight cycle. Unlike Dijkstra’s algorithm, it permits negative edge weights. Its standard implementation repeatedly relaxes all edges and can detect whether a negative-weight cycle is reachable from the source.

Problem and assumptions

Let G=(V,E)G=(V,E) be a directed graph with a finite vertex set VV, edge set EE, and edge-weight function w:E→Rw:E\to\mathbb{R}. Let s∈Vs\in V be the source.

The weight of a route is the sum of its edge weights. The shortest-path distance δ(s,v)\delta(s,v) is conventionally understood as the infimum of the weights of all directed walks from ss to vv. Three outcomes are possible:

  • Finite distance: a minimum-weight route exists.
  • Unreachable vertex: no route exists, represented by +∞+\infty.
  • Unbounded-below distance: a negative-weight cycle can be reached from ss, and vv can be reached from that cycle, so repeating the cycle makes the route weight arbitrarily small. This is represented mathematically by −∞-\infty.

A negative-weight cycle is a directed cycle whose edge weights sum to a negative number. Negative edges alone do not prevent finite shortest paths.

The standard Bellman–Ford procedure either returns distances when no negative cycle is reachable from ss, or reports a reachable negative cycle. An extended implementation can also identify exactly which vertices have distance −∞-\infty.

For an undirected graph represented by two oppositely directed edges per connection, any negative-weight edge creates a negative closed walk: it can be traversed in both directions repeatedly. Consequently, negative edges in undirected graphs require particular care when interpreting the problem.

Relaxation

The algorithm maintains a tentative distance d[v]d[v] for every vertex and, optionally, a predecessor π[v]\pi[v] for reconstructing routes.

Initially,

d[s]=0,d[v]=+∞for v≠s.d[s]=0,\qquad d[v]=+\infty\quad\text{for }v\ne s.

To relax an edge (u,v)(u,v), the algorithm checks whether reaching uu and then following that edge improves the current distance to vv:

if d[u]≠+∞ and d[u]+w(u,v)<d[v],\text{if }d[u]\ne+\infty \text{ and }d[u]+w(u,v)<d[v],

then it sets

d[v]←d[u]+w(u,v),π[v]←u.d[v]\leftarrow d[u]+w(u,v), \qquad \pi[v]\leftarrow u.

A relaxation never increases a tentative distance. Every finite value produced corresponds to the weight of an actual walk from the source. The difficulty is determining how many repetitions are sufficient to propagate all necessary improvements.

Dynamic-programming interpretation

Bellman–Ford can be understood through dynamic programming. Let Dk(v)D_k(v) be the minimum weight of a walk from ss to vv using at most kk edges. Then

D0(v)={0,v=s,+∞,v≠s,D_0(v)= \begin{cases} 0,&v=s,\\ +\infty,&v\ne s, \end{cases}

and

Dk(v)=min⁡(Dk−1(v),min⁡(u,v)∈E[Dk−1(u)+w(u,v)]).D_k(v)= \min\left( D_{k-1}(v), \min_{(u,v)\in E} \left[D_{k-1}(u)+w(u,v)\right] \right).

A direct implementation of this recurrence uses a previous-round array and a current-round array.

The common implementation instead updates one distance array in place while scanning the edges. Consequently, an improvement may propagate through several edges during a single pass, depending on edge order. Its values after pass kk need not equal Dk(v)D_k(v), but they are at least as good: every shortest route using at most kk edges has been accounted for by the end of that pass.

If no negative cycle is reachable from the source, any walk can have its cycles removed without increasing its weight. A shortest route can therefore be chosen to be simple, containing at most ∣V∣−1|V|-1 edges. This explains the algorithm’s standard pass limit.

Standard procedure

The following pseudocode uses in-place relaxation and stops early if an entire pass makes no change:

BellmanFord(V, E, w, s):
    for each vertex v in V:
        d[v] = infinity
        predecessor[v] = none
    d[s] = 0

    for i = 1 to |V| - 1:
        changed = false

        for each edge (u, v) in E:
            if d[u] != infinity and d[u] + w(u, v) < d[v]:
                d[v] = d[u] + w(u, v)
                predecessor[v] = u
                changed = true

        if not changed:
            return d, predecessor

    for each edge (u, v) in E:
        if d[u] != infinity and d[u] + w(u, v) < d[v]:
            return "negative-weight cycle reachable from source"

    return d, predecessor

The final scan tests for an improvement; it need not actually update the distances. Early termination is valid because a complete pass without changes establishes that every edge already satisfies its relaxation inequality.

When finite distances have been obtained, a route to a reachable target can be reconstructed by following predecessors backward to ss and reversing the resulting sequence.

Correctness

Two central properties explain the algorithm’s correctness.

First, every finite tentative distance is the weight of some source-to-vertex walk. Thus, where the true shortest-path distance is finite, a tentative value cannot be smaller than it.

Second, after kk complete passes, the algorithm has found values no greater than the weights of all source-to-vertex routes using at most kk edges. This can be established inductively along each route and expressed as a loop invariant.

If no reachable negative cycle exists, each reachable vertex has a shortest simple path with at most ∣V∣−1|V|-1 edges. After that many passes, the two properties force each tentative distance to equal the corresponding shortest-path distance.

Why an extra improvement signals a negative cycle

After ∣V∣−1|V|-1 passes, any remaining successful relaxation implies the existence of a reachable negative cycle. Without such a cycle, shortest simple paths would already provide the final distances.

Conversely, suppose a reachable negative cycle exists. All its vertices become reachable in the distance labels after enough passes. If none of its edges could be relaxed, each cycle edge would satisfy

d[v]≤d[u]+w(u,v).d[v]\le d[u]+w(u,v).

Adding these inequalities around the cycle cancels the distance terms and gives

0≤∑cyclew(u,v),0\le \sum_{\text{cycle}} w(u,v),

contradicting the cycle’s negative total weight.

The reachability condition matters: a negative cycle in a disconnected or otherwise unreachable part of the graph does not affect a run from ss.

Worked example

Consider the directed edges

s→a:4,s→b:5,a→b:−2,b→c:3.s\to a:4,\qquad s\to b:5,\qquad a\to b:-2,\qquad b\to c:3.

Using the synchronous dynamic-programming formulation, the distance table is:

Maximum edges allowed ss aa bb cc
0 0 +∞+\infty +∞+\infty +∞+\infty
1 0 4 5 +∞+\infty
2 0 4 2 8
3 0 4 2 5

The shortest route to cc is

s→a→b→c,s\to a\to b\to c,

with total weight

4−2+3=5.4-2+3=5.

An in-place implementation may obtain these final values sooner if its edge order allows improvements to propagate within the same pass.

If an edge c→ac\to a of weight −2-2 is added, then the cycle

a→b→c→aa\to b\to c\to a

has total weight −2+3−2=−1-2+3-2=-1. Because it is reachable from ss, the distances to aa, bb, and cc become unbounded below. The distance to ss remains 00, because the graph provides no route from that cycle back to ss.

Complexity and implementation issues

The standard algorithm makes up to ∣V∣−1|V|-1 full edge scans and one additional detection scan. Its usual worst-case time complexity is stated as

O(∣V∣∣E∣).O(|V||E|).

Including initialization explicitly, a bound valid even for graphs with no edges is

O(∣V∣+∣V∣∣E∣).O(|V|+|V||E|).

An edge-list representation is sufficient. Distance and predecessor arrays require O(∣V∣)O(|V|) auxiliary space, excluding storage for the graph. Storing all dynamic-programming rounds is unnecessary unless intermediate results are required.

Important implementation details include:

  • Infinity handling: an unreachable source endpoint must be skipped before adding an edge weight. A finite sentinel used as “infinity” must not accidentally participate in arithmetic.
  • Overflow: even when individual edge weights fit in an integer type, path sums may not.
  • Floating-point arithmetic: rounding can alter comparisons and make cycles with totals close to zero difficult to classify. Using a tolerance changes the exact mathematical detection criterion.
  • Edge order: ordering can substantially change the number of passes before convergence, although it does not change the worst-case guarantee.
  • Strict updates: predecessors should normally change only when a strictly shorter distance is found. Updating predecessors on ties can complicate reconstruction.

Locating cycles and affected vertices

To extract a negative cycle, an implementation can perform actual relaxations in an additional pass and record an updated vertex. Following its predecessor pointer ∣V∣|V| times reaches a vertex on a predecessor cycle; continuing until a vertex repeats recovers the cycle, with the traversal reversed to obtain its directed order.

To identify all vertices whose distances are −∞-\infty, the algorithm can collect vertices improved during the additional pass and traverse forward from them using breadth-first search or depth-first search. This marks both the reachable negative cycles and their downstream vertices. Other reachable vertices can still have finite shortest-path distances.

Applications and related algorithms

Difference constraints

Bellman–Ford can test feasibility of inequalities of the form

xv−xu≤cuv.x_v-x_u\le c_{uv}.

Represent each inequality by an edge u→vu\to v of weight cuvc_{uv}, and add a new source with zero-weight edges to every vertex. A negative cycle indicates inconsistency, because summing the inequalities around it yields an impossible inequality. If no negative cycle exists, the computed distances provide a feasible assignment.

This connects the algorithm to mathematical optimization and constraint-based scheduling.

Routing

Bellman–Ford’s recurrence underlies distance-vector routing. Routers exchange distance estimates with neighbors and update their estimates by combining a link cost with a neighbor’s advertised distance.

Such protocols are distributed adaptations rather than literal executions of a centralized edge-scanning program. Their behavior under network changes introduces additional issues, including routing loops and the count-to-infinity problem. This is an important application in distributed computing.

Reweighting and arbitrage

Johnson’s algorithm uses Bellman–Ford to compute vertex potentials and detect negative cycles before reweighting a graph for repeated Dijkstra searches. The reweighted edges are nonnegative while shortest-path relationships are preserved.

Currency-exchange arbitrage can also be modeled using negative-cycle detection. Assigning an exchange rate rr the weight −log⁡r-\log r transforms a cycle whose rate product exceeds 11 into a negative-weight cycle. Practical models must additionally account for transaction costs, numerical precision, and execution constraints.

Alternatives

Dijkstra’s algorithm is generally preferable when all edge weights are nonnegative. In a directed acyclic graph, topological-order relaxation finds shortest paths in O(∣V∣+∣E∣)O(|V|+|E|) time even with negative weights.

Queue-based variants process vertices whose distance changes may enable further relaxations. These can avoid many unnecessary scans in practice, but the commonly used shortest-path faster algorithm variant still has worst-case O(∣V∣∣E∣)O(|V||E|) time.

Historical development

The algorithm is named after Richard Bellman and Lester R. Ford Jr. Ford described a related method in 1956, and Bellman published his dynamic-programming formulation in 1958. Edward F. Moore independently presented a related shortest-path method in 1959, accounting for the alternative name Bellman–Ford–Moore algorithm.

These formulations established repeated relaxation as a central technique for shortest-path computation, connecting graph algorithms, dynamic programming, and distributed routing.