Shortest Paths: Bellman-Ford

What we are trying to do

A graph is a set of points, called vertices (or nodes), joined by connections, called edges. When each edge carries a number, that number is its weight, and it usually means a cost: a distance, a price, a delay. When an edge has a direction (it goes from one vertex to another, not both ways) we call the graph directed. We will draw edges as arrows.

The single-source shortest paths problem is this: pick one starting vertex, called the source, and find, for every other vertex, the cheapest total weight to reach it from the source. “Cheapest” means the sum of edge weights along the path is as small as possible.

The twist in this lesson is negative edge weights: an edge whose weight is a negative number. Negative weights are real. An edge might represent a leg of a trip that earns you money, or a chemical reaction that releases energy, or a currency trade that gains value. Many fast shortest-path methods quietly assume every weight is zero or positive and break when that is not true. Bellman-Ford is the method that keeps working when some edges are negative, and it can also tell you when the problem has no sensible answer at all.

The one graph we will use

Here is a small directed, weighted graph with four vertices labelled 0, 1, 2, 3. The source is 0. Notice the edge from 2 to 1 has weight -3.

flowchart LR
    N0((0)) -->|5| N1((1))
    N0((0)) -->|4| N2((2))
    N2((2)) -->|-3| N1((1))
    N1((1)) -->|3| N3((3))
    N2((2)) -->|6| N3((3))

Look at vertex 1. There is a direct edge 0 -> 1 costing 5. But there is also a longer route 0 -> 2 -> 1 costing 4 + (-3) = 1. The detour is cheaper because of the negative edge. Any method that grabbed the direct 5 and never reconsidered would get the wrong answer. The correct shortest distances from 0 turn out to be:

• to 0: 0 (you are already there)
• to 1: 1 (via 0 -> 2 -> 1)
• to 2: 4
• to 3: 4 (via 0 -> 2 -> 1 -> 3)

Our goal is a procedure that arrives at [0, 1, 4, 4] on its own.

The one operation: relaxing an edge

Everything in Bellman-Ford is built from a single small step called relaxation.

We keep a list dist, one number per vertex, holding the best distance found so far from the source to that vertex. At the start we know nothing, so every entry is set to infinity (a stand-in for “no path known yet”), except the source, which is 0 because reaching yourself costs nothing.

To relax an edge from u to v with weight w means: check whether going to u and then taking this edge beats the best route to v we have recorded. In plain arithmetic, ask whether

dist[u] + w < dist[v]

If yes, we just found a cheaper way to reach v, so we update dist[v] = dist[u] + w. If no, we leave dist[v] alone. One relaxation never makes anything worse; it only ever lowers a distance.

def relax(dist, u, v, w):
    # dist: current best distances; edge u -> v of weight w
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w

That is the whole engine. Bellman-Ford is nothing more than relaxing every edge, over and over, a controlled number of times.

Why relax every edge V minus 1 times

Here is the central idea. A shortest path from the source to any vertex, in a graph with no negative cycle (defined below), never needs to visit the same vertex twice. If it did, you could cut out the loop and the path would be no longer. A path that visits each of the V vertices at most once has at most V - 1 edges.

Now watch what one full round of relaxations does. Before any rounds, only the source has a correct distance (a path of 0 edges). After one round that relaxes every edge, every vertex reachable by a 1-edge shortest path is correct. After two rounds, every 2-edge shortest path is correct. Each round pushes the frontier of correct answers one edge further out, no matter what order the edges happen to be in. Since the longest shortest path has at most V - 1 edges, after V - 1 rounds every distance is final.

For our graph V = 4, so V - 1 = 3 rounds are enough.

Tracing it, one relaxation at a time

Relax the edges in this deliberately awkward order, chosen so the frontier of correct answers visibly crawls outward one hop per round:

1. 1 -> 3 weight 3
2. 2 -> 1 weight -3
3. 0 -> 2 weight 4
4. 0 -> 1 weight 5
5. 2 -> 3 weight 6

Start with dist = [0, ∞, ∞, ∞]. Each row below is one relaxation; the last column is the full dist array right after that step. “skip” means the source side is still infinity, so there is nothing to offer yet.

The compact view, showing only the state after each full round, makes the outward crawl obvious:

Round 1 settles the vertices one edge from the source. Round 2 lets the negative edge 2 -> 1 pull dist[1] down from 5 to 1. Round 3 carries that improvement one more hop, fixing dist[3]. This is exactly why a single pass is not enough and why V - 1 passes are: with this ordering, each round advances the answer by precisely one edge, and we needed all three.

The algorithm in full

def bellman_ford(n, edges, source):
    # n: number of vertices, labelled 0 .. n-1
    # edges: list of (u, v, w) meaning a directed edge u -> v of weight w
    # source: the starting vertex
    INF = float("inf")             # Python's stand-in for infinity
    dist = [INF] * n
    dist[source] = 0

    # Relax every edge, n - 1 times.
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    return dist

edges = [
    (1, 3, 3),
    (2, 1, -3),
    (0, 2, 4),
    (0, 1, 5),
    (2, 3, 6),
]
print(bellman_ford(4, edges, 0))   # -> [0, 1, 4, 4]

A few notes on the Python. float("inf") is a real value larger than any ordinary number, so any actual distance compares as smaller and wins. The for _ in range(n - 1) loop runs the body n - 1 times; the underscore is just a name we do not use. The inner for u, v, w in edges unpacks each (u, v, w) tuple into three variables at once. The guard dist[u] != INF says “only offer a route through u if we have actually reached u,” which keeps the meaningless infinity + w out of the comparison.

Detecting a negative cycle

A negative cycle is a loop of edges whose weights add up to a negative number. If one exists and is reachable from the source, the shortest-path problem has no answer: every time you go around the loop the total drops further, so there is no smallest total. Distances would fall toward negative infinity.

Bellman-Ford detects this for free. After the V - 1 rounds, every distance is final if no negative cycle exists. So do one more round. If any edge can still be relaxed, some distance is still dropping after it should have settled, which can only happen because of a negative cycle.

flowchart LR
    A((0)) -->|5| B((1))
    A((0)) -->|4| C((2))
    C((2)) -->|-3| B((1))
    B((1)) -->|-2| C((2))

The edges 2 -> 1 (-3) and 1 -> 2 (-2) form a loop 1 -> 2 -> 1 summing to -5, a negative cycle reachable from 0.

def bellman_ford(n, edges, source):
    INF = float("inf")
    dist = [INF] * n
    dist[source] = 0

    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # One extra pass. Any further improvement means a negative cycle.
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None

    return dist

good = [(1, 3, 3), (2, 1, -3), (0, 2, 4), (0, 1, 5), (2, 3, 6)]
print(bellman_ford(4, good, 0))                       # -> [0, 1, 4, 4]

cyclic = [(0, 1, 5), (0, 2, 4), (2, 1, -3), (1, 2, -2)]
print(bellman_ford(3, cyclic, 0))                     # -> None

Returning None is a clear way to say “no valid shortest paths exist from this source.”

Cost: O(V*E) time, O(V) space

Let V be the number of vertices and E the number of edges.

Time. The outer loop runs V - 1 times. Inside it we touch every edge once, which is E work. Multiply: (V - 1) * E, which we write as O(V*E). The extra negative-cycle pass adds one more E, too small to change the bound. So the total is O(V*E): the number of relaxations is rounds times edges, and that is the whole story.

Space. Beyond the input, the only structure we keep is the dist list, one number per vertex, which is O(V). The edges themselves are given to us; we do not build extra copies. So the working memory grows only with the number of vertices.

How it compares to Dijkstra

Dijkstra’s algorithm is the other standard single-source shortest-path method. It is faster, running in about O((V + E) log V) time with a heap, because it settles vertices one at a time in increasing distance order and never revisits a settled one.

That speed comes from a promise: once Dijkstra locks in a vertex’s distance, no cheaper route can appear later. That promise holds only when every edge weight is zero or positive. A negative edge can make a longer-looking route turn out cheaper after the fact, exactly as 0 -> 2 -> 1 beat 0 -> 1 in our graph, and Dijkstra would already have committed to the wrong value.

The short rule: reach for Dijkstra when every weight is non-negative; reach for Bellman-Ford when they are not, or when you need to know whether a negative cycle is present.

Common pitfalls

• Running only one pass. A single round of relaxations settles only the vertices one edge from the source. You must repeat V - 1 times; the awkward-ordering trace above shows an answer that is still wrong after rounds one and two.
• Dropping the reached-yet guard. Keep dist[u] != INF in the test. With float("inf") the arithmetic happens to stay safe, but if you ever swap in a large plain integer as your “infinity”, then bigint + (negative weight) can dip below another vertex’s bigint and trigger a false update. The guard makes the intent explicit and portable.
• Forgetting the extra pass. Without the one final round, the function silently returns nonsense distances on a graph that actually contains a negative cycle. The extra pass is what turns “wrong answer” into an honest “no answer.”
• Treating an undirected negative edge as ordinary. An undirected edge of weight -2 is really two directed edges, u -> v and v -> u, both -2. Together they form a cycle of weight -4. Any negative undirected edge is automatically a negative cycle.
• Reporting a negative cycle that the source cannot reach. This method only flags cycles reachable from the source. A negative cycle sitting in a disconnected corner does not affect these particular shortest paths and will not be detected here.
• Confusing V - 1 with E - 1. The number of rounds is tied to the number of vertices, not edges. A graph can have far more edges than vertices.

Practice

1. Add a parent list alongside dist. Whenever you relax edge u -> v, record parent[v] = u. After the algorithm finishes, write a small loop that follows parent backward from a target vertex to the source and prints the actual shortest path, not just its length.
2. Take the four-edge cyclic graph above and hand-trace three full rounds of relaxation, writing the dist array after each round. Confirm that at least one edge still relaxes on a fourth pass, which is what the detector keys on.
3. Change the weight of edge 2 -> 1 in the main graph from -3 to +3 and predict the new shortest distances before running the code. Explain why every distance is now reachable by a route that Dijkstra would also have found.