Bellman–Ford Algorithm

The Bellman–Ford algorithm finds the shortest paths from one starting vertex to every other vertex in a weighted graph. Its important advantage over Dijkstra’s algorithm is that it can handle negative edge weights and detect negative-weight cycles.

The problem

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 core idea: relaxation

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 the distance:

distance[v] = distance[u] + w

This process is called relaxation.

The algorithm

A simple path can contain at most |V| − 1 edges, where |V| is the number of vertices. Bellman–Ford therefore relaxes every edge |V| − 1 times. After the first pass it can discover paths using one edge; after the second, paths using two edges; and so on.

Set the source distance to 0.
Set every other distance to infinity.
Repeat |V| − 1 times, relaxing every edge.
Examine every edge once more to detect a negative-weight cycle.

BellmanFord(graph, source):
    for each vertex v:
        distance[v] = infinity
        predecessor[v] = undefined

    distance[source] = 0

    repeat |V| - 1 times:
        changed = false

        for each edge (u, v, weight):
            if distance[u] is not infinity
               and distance[u] + weight < distance[v]:

                distance[v] = distance[u] + weight
                predecessor[v] = u
                changed = true

        if changed is false:
            break

    for each edge (u, v, weight):
        if distance[u] is not infinity
           and distance[u] + weight < distance[v]:
            report negative-weight cycle

    return distance, predecessor

Negative-weight cycles

A negative-weight cycle is a cycle whose total edge weight is negative:

A → B = 2
B → C = -5
C → A = 1

The total is −2. If this cycle is reachable from the source, there is no well-defined shortest path: travelling around it repeatedly reduces the total cost indefinitely.

Bellman–Ford detects this by performing one additional pass after the normal |V| − 1 passes. If any distance can still be improved, a reachable negative-weight cycle exists.

Python implementation

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

def bellman_ford(vertices, edges, source):
    distances = {vertex: float("inf") for vertex in vertices}
    predecessors = {vertex: None for vertex 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.

Bellman–Ford versus Dijkstra

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.

Conclusion

Bellman–Ford is a fundamental shortest-path algorithm for weighted graphs. Its repeated relaxation process is straightforward to implement, while its support for negative weights and negative-cycle detection makes it useful when Dijkstra’s assumptions do not hold.

Bellman–Fordalgorithm