---
title: 'Bellman–Ford Algorithm'
source: 'https://academia.sh/en/courses/algorithms/bellman-ford-algorithm'
course: Algorithms
language: en
updated: '2026-08-17T18:07:36+00:00'
license: 'CC BY-SA 4.0'
---

# Bellman–Ford Algorithm

Relaxation by iterating over all edges, induction on edge count, negative cycle detection, and the linear solution on a directed acyclic graph.

Dijkstra's algorithm never returned to a vertex once it was settled; this was a gain
that rested on weights being non-negative. If a negative weight exists, a vertex's
value can drop later, and a single pass is not enough.

Bellman–Ford abandons this assumption: it settles no vertex, and instead relaxes **all
edges, repeatedly**.

## The Algorithm

All distances except the source start at infinity. Then $V-1$ passes are made over all
edges; each pass relaxes every edge once.

```python
def bellman_ford(graph: dict[str, list[tuple[str, int]]],
                 source: str) -> tuple[dict[str, float], bool]:
    """Returns (distances, whether a negative cycle exists)."""
    distance: dict[str, float] = {vertex: float("inf") for vertex in graph}
    distance[source] = 0
    edges = [(v, w, weight) for v in graph for w, weight in graph[v]]

    for _ in range(len(graph) - 1):
        changed = False
        for v, w, weight in edges:
            if distance[v] + weight < distance[w]:
                distance[w] = distance[v] + weight
                changed = True
        if not changed:                 # early exit: nothing improved
            break

    for v, w, weight in edges:          # one more pass, if it still improves
        if distance[v] + weight < distance[w]:
            return distance, True
    return distance, False


with_negative_weight = {
    "A": [("B", 1), ("C", 2)],
    "B": [("D", 1)],
    "C": [("B", -2)],
    "D": [],
}

print(bellman_ford(with_negative_weight, "A"))
# ({'A': 0, 'B': 0, 'C': 2, 'D': 1}, False)
```

The `D` distance that the previous lesson's Dijkstra computed incorrectly comes out
correct here: 1. The difference is that `B`'s outgoing edges are relaxed again after
its value drops.

The same algorithm is also correct on graphs without negative weight; Dijkstra's edge
is not correctness but speed.

## Why $V-1$ Passes

The justification is induction on the edge count of a path.

**Claim:** After the $k$-th pass, every shortest path using at most $k$ edges has been
computed correctly.

The base case is $k = 0$: the source's distance is zero. For the step, let the last
edge of a shortest path with at most $k+1$ edges be $(v, w)$. The portion of the path
up to `v` uses at most $k$ edges and, by the induction hypothesis, is correct after the
$k$-th pass; when this edge is relaxed on the $(k+1)$-th pass, `w` also gets its
correct value.

If there is no negative cycle, no shortest path visits a vertex twice, so it contains
at most $V-1$ edges. This is why $V-1$ passes suffice.

The early exit noticeably reduces the number of passes in practice: if no value
improved in one pass, later passes will not improve anything either.

## Negative Cycle

If an edge still relaxes after $V-1$ passes, a **negative cycle** reachable from the
source exists.

```python
cyclic = {
    "A": [("B", 1)],
    "B": [("C", -3)],
    "C": [("B", 1)],           # B → C → B cycle: -3 + 1 = -2
}

print(bellman_ford(cyclic, "A")[1])      # True
```

In such a cycle the problem is **undefined**: the total cost drops every time the
cycle is traversed, so there is no such thing as "the shortest path." Detection is done
not to salvage the computed values, but to report the problem itself.

The ability to detect negative cycles is not a byproduct — it is one of the algorithm's
main uses. The classic application is detecting arbitrage: if the multiplicative gain
of exchange rates is converted to additive cost by a $-\log$ transform, a profitable
cycle becomes a negative cycle, and the algorithm finds it.

## Marking the Affected Vertices

Knowing that a negative cycle exists is often not enough; **which vertices** are
affected by it is also asked. The distance of every vertex reachable from the cycle can
be made arbitrarily small, that is, negative infinity; the values of the remaining
vertices are valid.

The distinction is made by running $V-1$ more passes and marking the targets of edges
that still relax as negative infinity.

```python
def bellman_ford_marked(graph: dict[str, list[tuple[str, int]]],
                        source: str) -> dict[str, float]:
    distance: dict[str, float] = {vertex: float("inf") for vertex in graph}
    distance[source] = 0
    edges = [(v, w, weight) for v in graph for w, weight in graph[v]]

    for _ in range(len(graph) - 1):
        for v, w, weight in edges:
            if distance[v] + weight < distance[w]:
                distance[w] = distance[v] + weight

    for _ in range(len(graph) - 1):      # propagate negative infinity
        for v, w, weight in edges:
            if distance[v] != float("inf") and (
                distance[v] + weight < distance[w] or distance[v] == float("-inf")
            ):
                distance[w] = float("-inf")
    return distance


wide_cycle = {
    "A": [("B", 1)],
    "B": [("C", -3)],
    "C": [("B", 1), ("D", 2)],
    "D": [],
    "E": [("A", 1)],          # unreachable from the source
}

print(bellman_ford_marked(wide_cycle, "A"))
# {'A': 0, 'B': -inf, 'C': -inf, 'D': -inf, 'E': inf}
```

Three separate cases appear in the same dictionary: a valid distance (`A`), vertices
affected by the negative cycle (`B`, `C`, `D`), and an unreachable vertex (`E`). Code
that uses a result must distinguish all three cases.

## Cost

Every pass processes all edges, and at most $V-1$ passes are made:

$$
O(V \cdot E)
$$

This is noticeably more expensive than Dijkstra's $O((V+E)\log V)$. The space cost is
$O(V)$.

| Criterion | Dijkstra | Bellman–Ford |
|---|---|---|
| Negative weight | Not accepted | Accepted |
| Negative cycle | Not detected | Detected |
| Cost | $O((V+E)\log V)$ | $O(V \cdot E)$ |
| Approach | Greedy | Iterative relaxation |

The choice is clear: Dijkstra when weights cannot be negative, Bellman–Ford when they
can. If distances between all pairs of vertices are needed, algorithms designed for
all pairs at once are used instead of running each vertex separately; these are the
subject of the Advanced Algorithms course.

## A Cheaper Path in Acyclic Graphs

If the graph is **directed and acyclic (a DAG)**, a single pass suffices once the
relaxation order is chosen correctly, since there is no cycle. The correct order is the
topological order from the Data Structures course: when a vertex is processed, every
edge arriving at it has already been relaxed.

```python
def dag_shortest_path(graph: dict[str, list[tuple[str, int]]],
                      order: list[str], source: str) -> dict[str, float]:
    """order: a topological order. Cost O(V + E)."""
    distance: dict[str, float] = {vertex: float("inf") for vertex in graph}
    distance[source] = 0
    for v in order:
        if distance[v] == float("inf"):
            continue
        for w, weight in graph[v]:
            if distance[v] + weight < distance[w]:
                distance[w] = distance[v] + weight
    return distance


graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("C", 5), ("D", 10)],
    "C": [("E", 3)],
    "D": [("F", 11)],
    "E": [("D", 4)],
    "F": [],
}

print(dag_shortest_path(graph, ["A", "B", "C", "E", "D", "F"], "A"))
# {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20}
```

The result is the same one Dijkstra's algorithm finds on the same graph; the cost,
however, drops to $O(V + E)$. Moreover, this method also accepts **negative weights**,
because it makes no greedy choice.

The same structure is also used to find the **longest** path: the comparison direction
is reversed. In general graphs the longest path problem is hard; acyclicity makes it
linear. The critical path calculation in project planning is of this kind.

## Summary

- Bellman–Ford settles no vertex; it relaxes all edges over $V-1$ passes.
- After the $k$-th pass, every shortest path with at most $k$ edges is correct; without
  a negative cycle, a shortest path contains at most $V-1$ edges.
- An edge that still relaxes on the $V$-th pass means a negative cycle reachable from
  the source, and the problem is undefined.
- The cost is $O(V \cdot E)$; the early exit reduces the number of passes in practice.
- Dijkstra is chosen when weights cannot be negative, Bellman–Ford when they can.
- In acyclic graphs, a single pass in topological order suffices, and the cost is
  $O(V + E)$.

## Next Step

Both algorithms so far searched without a target: distance was computed from the
source to **every** vertex. This is wasteful if a specific target is the goal. The
next lesson narrows the search with an estimating function that knows the target's
direction — the A* algorithm — and examines the condition under which the estimate
does not break correctness.