Bellman–Ford Algorithm

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.

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.

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.

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.

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.