Bellman-Ford Calculator

Pseudocode

Bellman-Ford is the shortest-path algorithm that gives up cleverness in exchange for generality. There is no priority queue and no ordering decision, just repeated relaxation of every edge.

BellmanFord(graph, source):
    for each vertex v: dist[v] = infinity
    dist[source] = 0

    repeat V - 1 times:
        changed = false
        for each edge (u, v, w):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                changed = true
        if not changed: break        // early exit

    // One extra pass detects negative cycles
    for each edge (u, v, w):
        if dist[u] + w < dist[v]:
            report negative cycle reachable from source

The invariant is that after pass i, every shortest path using at most i edges is correct. Since a shortest path in a graph with no negative cycle uses at most V - 1 edges, V - 1 passes settle everything. If a V-th pass still improves something, a path is getting shorter without bound, which is exactly what a negative cycle means.

Worked example, step by step

Run Bellman-Ford from A on a graph with a negative edge that Dijkstra would get wrong. Edges are relaxed in the fixed order listed below.

Example graph: Directed edges A to B (4), A to C (5), B to C (-3), C to D (2).

1. Initialise. dist = A 0, B infinity, C infinity, D infinity.
2. Pass 1. A to B sets dist[B] = 4. A to C sets dist[C] = 5. B to C offers 4 + (-3) = 1, better than 5, so dist[C] = 1. C to D sets dist[D] = 1 + 2 = 3. After one pass: A 0, B 4, C 1, D 3.
3. Pass 2. Every edge is tested again and nothing improves. With the early-exit check the algorithm stops here rather than running the remaining passes.
4. Negative cycle check. One more sweep over all four edges finds no further improvement, so there is no negative cycle reachable from A and the distances are final.
5. Why Dijkstra fails here. Dijkstra would settle C at distance 5 as soon as C came off the priority queue, because it assumes a settled node can never improve. The later B to C edge of weight -3 would then be ignored, and Dijkstra would report dist[C] = 5 and dist[D] = 7 instead of the correct 1 and 3.

Correct distances are A 0, B 4, C 1, D 3. The single negative edge is enough to break Dijkstra, and it is the reason Bellman-Ford exists.

Complexity, and where it comes from

Time: O(VE) · Space: O(V)

The algorithm performs V - 1 passes, and each pass relaxes all E edges once, giving O(VE). Space is one distance and one parent entry per vertex, so O(V), notably independent of E. On a dense graph where E approaches V squared, the running time approaches O(V cubed), which is why Bellman-Ford is reserved for cases where negative weights genuinely occur. The early-exit check, stopping as soon as a pass changes nothing, often finishes in a handful of passes on real graphs even though the worst case remains V - 1.

When to use Bellman-Ford Algorithm, and when not to

Bellman-Ford is strictly more general than Dijkstra and strictly slower. Pick it only when you actually need what it buys.

Common pitfalls

• Running only V - 1 passes and calling it done. Without the extra V-th pass you cannot distinguish correct distances from distances still falling through a negative cycle. The detection pass is not optional bookkeeping, it is what makes the output trustworthy.
• Assuming a reported negative cycle affects the whole graph. The extra pass only detects cycles reachable from the source. A negative cycle sitting in an unreachable component is invisible and, for single-source purposes, irrelevant. If you need all negative cycles, run from a virtual source connected to every vertex.
• Relaxing from vertices at infinite distance. In languages where infinity is a large integer rather than a float, dist[u] + w overflows and wraps negative, creating phantom improvements. Guard the relaxation with a check that dist[u] is not still infinite.
• Using it on nonnegative graphs out of caution. On a graph with no negative edges, Bellman-Ford computes exactly what Dijkstra does but can be orders of magnitude slower. Generality is not free.
• Expecting shortest paths to exist at all with a negative cycle. When a negative cycle is reachable, there is no shortest path, not merely an unknown one: you can always go round the cycle again and get lower. Report the cycle rather than returning a distance.

Frequently asked questions

What is the Bellman-Ford algorithm used for?

It computes shortest paths from a single source in graphs that may contain negative edge weights, and it detects negative cycles. In practice it backs distance-vector routing protocols such as RIP, currency arbitrage detection where exchange rates become negative logarithms, and scheduling problems where some transitions carry a gain rather than a cost.

Why use Bellman-Ford instead of Dijkstra?

Because Dijkstra is wrong on negative edges. Dijkstra permanently settles a node when it comes off the priority queue, assuming nothing can improve it later, and a negative edge discovered afterwards breaks that assumption. Bellman-Ford makes no such commitment, so it stays correct at the cost of O(VE) instead of O((V + E) log V).

How does Bellman-Ford detect negative cycles?

After V - 1 relaxation passes, every shortest path that can exist is already final, because a simple path has at most V - 1 edges. If one more pass over all edges still improves some distance, that improvement can only come from a cycle of negative total weight reachable from the source.

What is the time complexity of Bellman-Ford?

O(VE) time and O(V) space. It runs V - 1 passes over all E edges. With the early-exit optimisation it often stops far sooner on real graphs, but the worst case is unchanged. On dense graphs this approaches O(V cubed).

Can Bellman-Ford handle negative weights?

Yes, that is its entire purpose, provided no negative cycle is reachable from the source. With negative weights but no negative cycle it returns correct shortest paths. With a reachable negative cycle no shortest path exists, and the algorithm reports that rather than returning a meaningless distance.