Bellman–Ford Algorithm

Dijkstra is fast because it commits: the closest vertex is settled and never looked at again. Negative edges make that commitment unsafe. Bellman–Ford takes the opposite approach — it commits to nothing:

Relax every edge in the graph. Then do it again. And again — V − 1 times in total.

Relaxing an edge u → v of weight w means asking: "is going through u a shortcut to v?" — if dist[u] + w < dist[v], update dist[v].

Why V − 1 rounds? A shortest path never repeats a vertex, so it has at most V − 1 edges. And each full round of relaxations pushes correct distances at least one more edge along every shortest path:

• after round 1, every shortest path of ≤ 1 edge is correct,
• after round 2, every shortest path of ≤ 2 edges is correct,
• … after round V − 1, every shortest path is correct.

No priority queue, no settling, no cleverness — just patience. That's also why it handles negative weights: a vertex's distance is allowed to keep improving until the very last round.

One thing no algorithm can do is find shortest paths when a negative cycle is reachable: loop around a cycle of total weight −3 enough times and any path gets arbitrarily cheap. "Shortest path" simply isn't defined there.

Bellman–Ford detects this for free: after the V − 1 rounds, run one extra round. If any edge still relaxes — some dist still improves — distances haven't converged, and that is only possible if a negative cycle is reachable from the source.

The same trick gives an early exit in the other direction: if some round makes no changes at all, distances have already converged — stop immediately. Real inputs rarely need all V − 1 rounds.

Run Bellman–Ford from vertex 1 on this directed graph with negative edges. Step forward and backward with the ← / → arrow keys or the buttons below.

What to watch:

• The edge list is scanned top to bottom once per round (the round tracker shows progress). The dashed amber arrow is the edge currently being relaxed.
• A vertex flashes green the moment its distance improves. Watch dist[5]: it improves in every round — 5 → 2 → 0 — because its true shortest path 1 → 4 → 3 → 2 → 5 is 4 edges long, and each round can only push correct information one edge further.
• The green arrows are the current parent pointers — the best-known-path tree. Watch it rewire as cheaper routes are discovered (e.g. vertex 2's parent flips from 1 to 3).
• Round 4 makes no changes — that's the convergence signal, and it doubles as the proof that no negative cycle is reachable.

When to reach for Bellman–Ford:

• Edge weights can be negative (currency arbitrage, profit/cost edges, potentials).
• You need to detect negative cycles.
• The graph is small enough that O(V · E) is fine, and you value the 10-line implementation.

In contests, the queue-based variant SPFA often runs much faster in practice (same worst case), and Dijkstra remains the default whenever weights are guaranteed non-negative.

The whole algorithm is one nested loop — relax all edges, V − 1 times — plus the optional early exit and the negative-cycle check round. Note the guard dist[u] ≠ ∞: an edge out of an unreached vertex has nothing to offer yet (∞ + w is still ∞). The C++ tab runs the exact graph from the visualization.

The work is plain to count: each of the (up to) V − 1 rounds relaxes all E edges once.

• Time: O(V · E) worst case. With the early-exit check the typical case is far better — the loop stops as soon as a round changes nothing.
• Space: O(V) for dist[] and parent[] — the graph itself can stay as a flat edge list, the cheapest representation there is.

For comparison, on a sparse graph (E ≈ V) Bellman–Ford costs about V² operations where Dijkstra costs V log V. That gap is the price of supporting negative weights.