The Bellman–Ford algorithm
Also known as: Bellman–Ford algorithm · Bellman–Ford–Moore · SPFA · negative cycle detection · shortest paths with negative weights
Shortest paths when edges can have negative lengths: all edges are checked round after round, and after k rounds the best paths of at most k edges are known. If the improvements never stop, the graph has a cycle of negative length; on currency rates that is a round of exchanges that returns more than you started with.
On 9 October 2026 the National Bank announced that a euro costs 502.05 tenge, a rand (ZAR) 26.91 tenge and a peso (MXN) 24.89. The same day the ECB announced that a euro buys 18.527 rand or 20.395 pesos. Buy rand for a million tenge, euros for the rand, pesos for the euros, and sell the pesos back for tenge. That gives 1,018,192 tenge. The round can be repeated, and the million will grow without end. Below are all the rates of that day and an algorithm that finds such rounds.
Watch what happens to the first line under the picture. While the rates come from one source, only the National Bank or only the ECB, there is no profitable round: all rates go through the tenge or through the euro and agree with each other. Take both sources, and the sum in tenge starts growing from round to round. Move the fee slider: if every exchange costs 0.45 %, no profitable rounds remain.
The idea
First turn exchanges into a path. A rate is a multiplier: one unit of currency A buys r units of currency B, and the sum after several exchanges is a product of rates. A logarithm turns a product into a sum, and “more” into “less” if taken with a minus sign. Let the length of the edge A → B be −log r. Then the most profitable exchange is a shortest path, and a round that returns more than you started with is a cycle of negative length.
The lengths come out both positive and negative, and Dijkstra lies here: it declares a distance final, and a negative edge later reduces it. We need an algorithm that draws no premature conclusions.
Check all edges in a row and improve distances where possible: that is one round. After k rounds the shortest paths of at most k edges are known. A shortest path without cycles has at most V − 1 edges, so V − 1 rounds are enough. If the V-th round still improves something, the graph has a cycle of negative length, and there are no shortest paths: every turn around the cycle makes a path shorter still.
Each check is the same relaxation as in Dijkstra. The difference is the order: Dijkstra chooses which vertex to process next and therefore processes each one once. Bellman–Ford chooses nothing and simply repeats everything until nothing changes.
Rounds step by step
Here is the trap from the article on Dijkstra, the road C → B of length −3, and one more road, D → E. The rows of the table are the distances from A after each round.
With an unlucky order of edges, news of a short path travels one edge per round: first to B, then to D, then to E, and four rounds are needed. With a lucky one, when the edges stand in path order, one is enough. The answer does not depend on the order, only the time does. Now turn on the road E → C of length −1: the round C → B → D → E → C has length −3 + 1 + 2 − 1 = −1, and the fifth round improves something again. With five vertices this means a negative cycle.
Why it is correct
If the graph has no cycle of negative length reachable from the start, then after k rounds the distance to each vertex is at most the length of the shortest path to it of at most k edges, and after V − 1 rounds it equals the length of the shortest path. If there is such a cycle, improvements never stop in any round.
The first part is induction on k. Let the shortest path of at most k + 1 edges to v end with the edge (u, v). Its beginning up to u is a path of at most k edges, and after k rounds dist[u] is at most its length. In round k + 1 the edge (u, v) is checked, and dist[v] becomes at most the length of the whole path. Distances never drop below the real ones: every value of dist is the length of some real path. Without negative cycles the shortest path can be taken simple, and a simple path has at most V − 1 edges.
The second part. Let the cycle v0, v1, …, vm = v0 have negative length and be reachable, and let a round pass without improvements. Then for every edge of the cycle dist[vi] ≤ dist[vi−1] + wi. Add these m inequalities: the sums of dist on the left and right are equal, and what remains is 0 ≤ w1 + … + wm < 0. A contradiction.
It remains to extract the cycle itself. Every improvement remembers where it came from: parent[v] = u. If the V-th round improved a vertex x, the chain of parents back from x cannot end at the start within V − 1 steps, otherwise it would be a path already found by round V − 1, and somewhere it loops. Step back from x V times: this certainly gets us off the tail and onto the cycle itself. Then follow parent until we return to the same vertex.
The proof also says that Bellman–Ford is dynamic programming: the state is “vertex and number of edges”, the transition one edge. If the array of distances is copied before each round, after k rounds exactly the best “at most k edges” is known. Without the copy a round sometimes gets further; for shortest paths that is only a plus, but when the number of steps is limited by the statement it is a mistake. That is exactly what the second problem is about.
Code
The classic version: a list of edges, rounds until the first round without changes, and finding the cycle by parent. The demo is the same five crossroads.
And these are the rates of 9 October. The program builds a graph from the National Bank's rates, the ECB's, both together, and the ECB table re-based to each currency, looks for a profitable round, and finds by binary search the smallest fee at which there is none.
the ECB table re-based and rounded: TRY -> USD -> TRY gives +0.018% pairs that come back with more: 223 of 435, the best IDR -> RON -> IDR +1.299% a fee of 0.64% per exchange removes every cycle both sources: KZT -> ZAR -> EUR -> MXN -> KZT 1000000 KZT -> 1018192 KZT a fee of 0.45% per exchange removes every cycle
Where the “profit” comes from
The program has three findings, and none of them makes anyone richer.
One source: consistent rates. The National Bank announces the rate of each currency against the tenge, the ECB against the euro. Any round of exchanges within one source goes through the centre and back, and the product of rates on it is exactly 1. Bellman–Ford stops after the second round: there is no profitable round.
The same source, but rounded. The Frankfurter service re-bases the ECB table to any base currency and rounds the rates, and very small rates are left with two or three significant digits: the rupiah (IDR) to the leu (RON) comes out as 0.00027, and the leu to the rupiah 3751.83, and “buy and sell at once” gives +1.3 %. In the table of 435 pairs, 223 are like that. This is not profit but traces of rounding, and Bellman–Ford dutifully finds them first.
Two sources: two different moments. The ECB fixes its rates in the afternoon, at about 14:10 local time, while the National Bank sets the tenge rate by its own method and at its own time. Through the rand a euro costs 26.91 · 18.527 = 498.56 tenge, through the peso it can be sold for 24.89 · 20.395 = 507.63 tenge, and at the National Bank itself a euro costs 502.05. The difference of 1.8 % is the round in the scene. You cannot buy at such a rate: reference rates are published for information, and the ECB explicitly advises against using its own for transactions. A real exchange office takes a spread between buying and selling, and at a fee of 0.45 % per exchange the round disappears.
Hence a conclusion about the method itself. A negative cycle in a graph of rates means the rates are inconsistent, not that there is a ready way to make money. On exchanges such inconsistencies can be real, but they live for fractions of a second and have to account for fees and volumes that reference tables do not have.
Without a margin in the comparison, Bellman–Ford finds “arbitrage” even in the rates of the National Bank alone. The rate of QAR to the tenge is 123.17, the reverse 1/123.17, and their product is exactly 1. But −log 123.17 − log(1/123.17) in floating point equals −8.9 · 10−16, and without a margin this round looks profitable. Among the 48 rates there are seven such pairs. So in the listing an improvement counts only if it is greater than 10−12.
What it costs
Each round checks all E edges, and there are at most V rounds: O(V · E) time and O(V) memory. With early stopping there are as many rounds as edges in the longest of the shortest paths, plus one. On a road grid that is on the order of its side, √V, and the time is about E · √V. A measurement on grids with random lengths from 1 to 9 and shuffled edge order, next to Dijkstra:
All rounds give a slope of about 2, as V · E promises with E ≈ 2V. With early stopping about 1.6, close to V1.5. Dijkstra grows almost linearly and at ten thousand vertices in Python is 16 times faster. So Bellman–Ford is chosen only when negative edges really exist or the negative cycle itself is needed.
A common speed-up is a queue: check edges only out of vertices whose distance changed last time. Edward Moore described this variant back in 1959; in competitive programming it is known as SPFA. On random graphs it is usually faster, but the worst case remains O(V · E), and graphs on which the queue works slowly can be built.
Where it is used
Routing. In the RIP protocol each router knows only its neighbours and keeps telling them its distances to all networks: these are rounds of Bellman–Ford spread across different machines. RFC 1058 (1988) calls such algorithms distance-vector algorithms and notes that they are also known by the name of Bellman–Ford. It also describes the trouble with the distributed version, “counting to infinity”: when a network disappears, neighbours keep referring to each other and slowly raise the distance. That is why in RIP infinity is 16, and there are no routes longer than 15 hops.
Potentials. Johnson's algorithm runs Bellman–Ford once to pick for each vertex a number h(v) after which all lengths w(u, v) + h(u) − h(v) are non-negative, and then computes shortest paths with Dijkstra. It is the same trick that makes A* correct, reduced lengths.
Systems of difference constraints. A schedule where “job B starts at least 3 days after A” and “C no later than 5 days after B” is a set of inequalities of the form xv − xu ≤ c. Each is an edge u → v of length c, and the triangle inequality for shortest distances is exactly the same. A solution of the system is the distances from an added vertex connected to all others by edges of length 0, and if there is no solution, Bellman–Ford finds a negative cycle, a contradictory chain of requirements.
Minimum-cost flows. A flow can be improved as long as the residual network has a cycle of negative cost, and it is found the same way. More in the article on minimum-cost flow.
History
The algorithm was discovered several times almost simultaneously. Alfonso Shimbel described it in 1955, Lester Ford in 1956 in a RAND Corporation report on network flow theory, Richard Bellman in 1958 in the note “On a routing problem”, and Edward Moore in 1959, in the same work on finding a path through a maze that is recalled in the article on breadth-first search. So the algorithm is called now Bellman–Ford, now Bellman–Ford–Moore. Bellman derived it from the principle of optimality, that very dynamic programming: the shortest path to a vertex is made of the shortest path to a neighbour and one edge.
Problems
In the first problem you find a profitable round of exchanges or prove there is none, and the check is exact: among the tests are the rates of the National Bank alone, where there is no profit, but a program without a margin finds one. In the second the number of exchanges is limited, and a round without a copy of the array quietly makes extra ones.
A profitable round of exchanges At most k exchangesData: Exchange rates of 9 October 2026: the National Bank (tenge rates) and the ECB via Frankfurter