Bellman–Ford Algorithm

The Bellman–Ford algorithm finds the shortest paths from one starting vertex to every other vertex in a weighted graph. Unlike Dijkstra’s algorithm, it can handle negative edge weights and detect reachable negative-weight cycles.

What you will learn

By the end of this article, you should be able to:

explain relaxation in plain language;
trace Bellman–Ford on a small weighted graph;
distinguish a negative edge from a negative-weight cycle;
recognise when Bellman–Ford is a better fit than Dijkstra’s algorithm; and
implement the algorithm in Python.

The central idea

Bellman–Ford repeatedly examines every edge and asks whether reaching the destination through that edge produces a shorter path.

For an edge from u to v with weight w, it checks:

distance[u] + w < distance[v]

If the condition is true, it updates distance[v]. This operation is called relaxation.

A simple path can contain at most |V| − 1 edges, where |V| is the number of vertices. Repeating relaxation across every edge |V| − 1 times is therefore enough to discover every finite shortest path when no reachable negative cycle exists.

A worked example

Given a directed, weighted graph and a source vertex, we want to calculate the minimum cost of reaching every other vertex.

Consider these edges:

A → B = 4
A → C = 2
C → B = -1
B → D = 3
C → D = 7

The direct path from A to B costs 4. However:

A → C → B = 2 + (-1) = 1

So the shortest distance from A to B is 1.

The implementation stores predecessor vertices as well as distances, allowing the shortest route to be reconstructed later.

def bellman_ford(vertices, edges, source):
    # Both inputs are reused across several passes, so materialise one-shot
    # iterables such as generators before calculating distances.
    vertices = list(vertices)
    edges = list(edges)

    distances = {vertex: float("inf") for vertex in vertices}
    predecessors = {vertex: None for vertex in vertices}

    if source not in distances:
        raise ValueError("Source vertex is not in vertices")

    for start, end, _ in edges:
        if start not in distances or end not in distances:
            raise ValueError("Edge references a vertex not in vertices")

    distances[source] = 0

    for _ in range(len(vertices) - 1):
        changed = False

        for start, end, weight in edges:
            if distances[start] == float("inf"):
                continue

            candidate = distances[start] + weight

            if candidate < distances[end]:
                distances[end] = candidate
                predecessors[end] = start
                changed = True

        if not changed:
            break

    for start, end, weight in edges:
        if distances[start] == float("inf"):
            continue

        if distances[start] + weight < distances[end]:
            raise ValueError("Graph contains a negative-weight cycle")

    return distances, predecessors

For the example graph, the result from source A is:

{'A': 0, 'B': 1, 'C': 2, 'D': 4}

The shortest route to D is A → C → B → D, with total cost 2 + (−1) + 3 = 4.

A common misconception

A negative edge is not the same as a negative-weight cycle. A single negative edge can still belong to a perfectly valid shortest path. The problem arises when a reachable cycle has a negative total weight: travelling around that cycle repeatedly makes the path cost smaller without limit, so no finite shortest path exists.

Bellman–Ford checks for this after its normal passes. If any reachable distance can still be improved, the graph contains such a cycle.

Try it yourself

Using the example graph, start at A and work out the shortest distance to D. Which predecessor should be stored for D, and what complete route does that produce?

Answer

The shortest distance is 4. The last edge is B → D, so the predecessor of D is B. Following predecessors backwards gives D ← B ← C ← A, which reverses to the route A → C → B → D.

Its cost is:

2 + (-1) + 3 = 4

The direct alternative A → C → D costs 9, so it is not the shortest route.

Use it in practice

Dijkstra’s algorithm is usually faster, but it assumes that all edge weights are non-negative. Bellman–Ford is slower, yet supports negative edges and explicitly detects reachable negative-weight cycles.

Bellman–Ford: supports negative edges, detects negative cycles, and runs in O(VE) time.
Dijkstra: requires non-negative edges and can run in O((V + E) log V) time with a heap.

Use Dijkstra when all edge weights are non-negative and performance matters. Use Bellman–Ford when negative edges are possible or cycle detection is required.

Bellman–Ford is useful when costs can include credits, corrections, or other negative adjustments. Its negative-cycle check also makes the underlying data problem explicit: if repeated traversal can reduce the cost indefinitely, the model does not have a finite optimum.

Recursion without mystery develops the habit of reasoning from smaller subproblems.
Debugging as a teachable habit shows how small traces and explicit expectations make algorithms easier to inspect.