• V = number of vertices, E = number of edges
• Edge weights may be negative
• The graph must be directed — a negative edge in an undirected graph is itself a negative cycle
• Shortest paths exist only when no negative cycle is reachable from the source
• O(V × E) time and O(V) space

Dijkstra's algorithm is faster than this one and handles most graphs. Understanding Bellman-Ford is really about understanding the one situation Dijkstra cannot handle, and why that situation demands a completely different strategy.

Dijkstra works by settling vertices in increasing order of distance and never reconsidering them. Its correctness rests on one claim: when u is the nearest unsettled vertex at distance d, no cheaper route to u can exist, because any alternative route would have to leave through some other unsettled vertex already at distance d or more, and the remaining segment cannot reduce the total.

That last step assumes remaining segments cost at least zero.

Give it edges (0,1,4), (0,2,5) and (1,2,-3), and watch it fail. Dijkstra settles vertex 0 at 0, then finds vertex 1 tentatively at 4 and vertex 2 tentatively at 5. The nearest unsettled is vertex 1 at 4, so it settles — fine. Relaxing 1→2 gives 4 + (-3) = 1, improving vertex 2 to 1. In this small graph the update happens to land before vertex 2 is settled, so the answer comes out right; rearrange the weights so vertex 2 is settled first and it does not. The general point stands: once a negative edge exists, "nearest so far" no longer means "final", and an algorithm built on never revisiting a settled vertex has no way to recover.

So the fix cannot be a smarter order of settling. It has to be an approach that revisits everything.

Stop trying to finalise vertices one at a time. Instead, ask a different question: what is the shortest path to each vertex using at most one edge? Then at most two edges? Then three?

The one-edge answers are immediate — just the direct edges from the source. And the k-edge answers follow from the (k-1)-edge answers: a shortest path using at most k edges is a shortest path using at most k-1 edges to some vertex u, plus one final edge from u.

That step is called relaxation. Relaxing edge (u, v, w) means: if the current known distance to u plus w beats the known distance to v, record the improvement.

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

Relaxing every edge once is a full pass, and each pass guarantees that all shortest paths of one more edge have been found. Because the update writes into the same array being read, a single pass can sometimes propagate further than one edge — which only ever helps and never hurts correctness.

How many passes are needed? Exactly as many edges as the longest shortest path can contain.

A shortest path never visits a vertex twice. If it did, the segment between the two visits forms a cycle, and — assuming no negative cycles — removing that segment gives a path no longer than the original, so a shortest path can always be chosen without repeats. A path visiting V vertices without repetition has V-1 edges.

So V-1 passes suffice, and that count is tight: a graph shaped as a single chain of V vertices, with edges listed in the worst possible order, genuinely needs all V-1.

def bellman_ford(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0

    for _ in range(V - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                              # settled early; further passes do nothing

    for u, v, w in edges:                      # one extra pass: the cycle test
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None                        # still improving: negative cycle
    return dist

Now the second capability, which Dijkstra has no analogue for.

Suppose a cycle's weights sum to a negative number. Then any path reaching that cycle can go round it again and reduce its total, and again, without limit. Shortest paths to those vertices are undefined — not merely hard to compute, but genuinely nonexistent.

The detection is elegant. After V-1 passes, every genuine shortest path has been found, because none can use more than V-1 edges. So run one more pass. If any edge can still be relaxed, some path is still improving after V-1 edges — meaning it must repeat a vertex, and repeating a vertex to gain improvement means the repeated segment has negative weight. That is a negative cycle, proven rather than guessed.

Note this detects cycles reachable from the source. A negative cycle elsewhere in the graph never affects these distances and is not found. Detecting any negative cycle anywhere requires adding a virtual source with a zero-weight edge to every vertex.

Vertices 0 to 3, edges (0,1,5), (1,2,2), (1,3,-4), (3,2,1), source 0. Edges are processed in that order each pass.

Start: dist = [0, ∞, ∞, ∞].

Pass 1.
- (0,1,5): 0 + 5 = 5 beats ∞, so dist[1] = 5.
- (1,2,2): 5 + 2 = 7 beats ∞, so dist[2] = 7.
- (1,3,-4): 5 + (-4) = 1 beats ∞, so dist[3] = 1. The negative weight causes no trouble at all.
- (3,2,1): 1 + 1 = 2 beats the 7 just written, so dist[2] = 2. Note this improvement happened within the same pass, because dist[3] had already been updated a moment earlier — passes can propagate further than one edge when the edge order is favourable.

dist = [0, 5, 2, 1].

Pass 2. Every edge is tried again and none improves anything: 0 + 5 is not below 5, 5 + 2 = 7 is not below 2, 5 - 4 = 1 is not below 1, 1 + 1 = 2 is not below 2. The changed flag stays false and the loop exits early after 2 of the 3 permitted passes.

Cycle test. One more full pass, and again nothing relaxes. No negative cycle. Final distances [0, 5, 2, 1].

Now the negative-cycle case: edges (0,1,1), (1,2,-1), (2,1,-1), source 0. Pass 1 sets dist[1] = 1, then dist[2] = 0, then relaxes (2,1,-1) to give dist[1] = -1. Pass 2 pushes dist[2] to -2 and dist[1] to -3. Each pass drives both lower by 2, and the final test pass still finds an improvement available, so the algorithm reports a negative cycle. Correct: the loop 1 → 2 → 1 sums to -2.

Three tools, and the choice is mechanical once you check two properties.

All weights non-negative, single source — use Dijkstra. At O((V + E) log V) it is far faster than O(V × E).

Any negative weight, single source — use Bellman-Ford. It is the only single-source option, and it also tells you whether the question is well posed at all.

All pairs of vertices — use Floyd-Warshall at O(V³), which also tolerates negative edges. Running Bellman-Ford from every vertex would cost O(V² × E), which is worse on dense graphs.

Where negative weights genuinely arise is worth knowing, since they sound artificial. Currency arbitrage is the classic: take the negative logarithm of each exchange rate, and a sequence of trades that multiplies your money becomes a negative cycle. Others include chemical reactions that release energy, game scoring where some moves give points back, and any cost model with rebates.

SPFA is the standard optimisation worth naming. Only vertices whose distance changed in the previous pass can cause further improvements, so keep those in a queue and relax only their outgoing edges. Typically much faster; the worst case is unchanged.

Train the reflex: check the sign of the weights before choosing a shortest-path algorithm. One negative edge invalidates the greedy method entirely, and the replacement costs a factor of V — but it answers a question the greedy method cannot even ask, namely whether a shortest path exists at all.