---
title: "Bellman–Ford Algorithm — Erkan Malcok"
description: "A clear guide to the Bellman–Ford algorithm, including relaxation, negative edges, negative cycles, complexity, and a Python implementation."
date: "2026-08-26"
updated: "2026-09-02"
canonical: "https://erkanmalcok.com/articles/bellman-ford-algorithm/"
kind: "Article"
series: "algorithms"
tags:
  - "Computer science"
  - "Algorithms"
---

# Bellman–Ford Algorithm — Erkan Malcok

Finding shortest paths when edge weights can be negative.

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.

```python
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.

## Related reading

- [Recursion without mystery](/articles/recursion-without-mystery/) develops the
  habit of reasoning from smaller subproblems.
- [Debugging as a teachable habit](/articles/debugging-as-a-teachable-habit/)
  shows how small traces and explicit expectations make algorithms easier to
  inspect.