The bound with a precondition

There are two shortest-path algorithms in every course. Dijkstra’s is $O(E \log V)$ and requires non-negative weights. Bellman–Ford is $O(VE)$ and does not.

That is a clean trade and it is stated as one: pay a factor of roughly $V/\log V$ for the generality. On a graph of two thousand vertices that is a factor of about two hundred, so the advice writes itself — use Dijkstra unless there are negative weights.

Both halves of the trade turn out to be misstated, in opposite directions, and each of them is a different kind of misstatement.

The bound describes a version nobody runs #

Bellman–Ford’s structure is: relax every edge, $V-1$ times. The bound is the product of those two numbers and it is tight, in the sense that inputs exist requiring all $V-1$ passes.

Every implementation of it also contains an early exit — if a pass changes nothing, stop, because no later pass can change anything either. It is two lines, it costs one boolean, and it appears in the pseudocode in the original papers.

How many passes it actually takes, on the graphs here:

The number of passes is essentially the graph’s diameter in hops — the number of edges on the longest shortest path — because each pass propagates distance information one hop further. A random sparse graph has a diameter around $\log V$; a grid has $\sqrt V$ but its useful diameter under relaxation in index order is much lower; a dense graph has diameter two.

None of those is $V$. $V$ is the diameter of a path graph, and the next section is about how the path graph turns out not to be enough either.

So the measured cost is not $VE$ and the fit says so, loudly: work ÷ $VE$ varies by a factor of 18.45 on the sparse sweep, 15.18 on the dense one and 11.14 on the grid. The class is refused in every regime, and the algorithm carries no declared complexity class on this site at all.

That is the most complete withdrawal in the collection. Bubble sort lost one entry; the hybrid lost one; this lost three.

The version that does fit #

The site also carries Bellman–Ford with the early exit removed — the algorithm the bound is exactly about. It fits $VE$ at a spread of 1.01 in all three regimes, which is as close to a perfect fit as anything here achieves.

Two implementations of one algorithm. One of them fits its famous bound to within one percent and one of them does not fit it within a factor of eighteen, and the difference between them is a boolean.

This is the same discovery as the queue, arriving from a different direction: the published complexity describes a specific program, the pseudocode does not determine which program, and the gap between the candidates is orders of magnitude. There it was an initialisation loop. Here it is a break.

The right conclusion is not that the bound is wrong — it is a worst-case bound and the worst case is real. It is that quoting a worst-case bound as a description of behaviour is a category error, and this pair makes the error measurable rather than arguable. Anybody comparing Bellman–Ford against Dijkstra using the published classes is comparing $E\log V$ against $VE$ and getting a factor of two hundred. Measured on a sparse graph of 2,048 vertices, Dijkstra with a heap costs 56,973 units and Bellman–Ford costs 174,080. The real factor is 3.06.

The worst case is not a graph, it is an order #

The obvious way to reach $V-1$ passes is a path: a chain of $V$ vertices where distance information can only travel one hop per pass. Running Bellman–Ford on one:

Two passes, on the shape that is supposed to be the worst case.

The reason is that this implementation relaxes vertices in index order, 0 upwards, and the path’s vertices are numbered along it. So a single forward sweep carries the distance from vertex 0 to vertex 1 to vertex 2 and all the way to the far end, in one pass. The second pass confirms nothing changed. The graph’s diameter is $V-1$ and the algorithm never notices, because it happens to walk the edges in the order the information wants to travel.

Reverse the sweep — relax vertices from the far end backwards, on the same path, with the same weights — and:

Every pass allowed, used, with exactly one distance improved per pass. That is the worst case, attained exactly, and reaching it required changing the direction of a loop rather than changing the graph.

Three things fall out of that, and the third is the one this essay is really about.

The bound is over inputs and implementations jointly. $O(VE)$ is a worst case over graphs and over relaxation orders, and no statement of it mentions the second. A reader who tests on a path and concludes that the bound is pessimistic has tested the wrong variable.

The good order is not available in general. The forward sweep works on a path because the vertices happen to be numbered along it. On a graph with no such numbering there is no order that is good for every source, and finding one for a given source means computing the traversal order — which is the problem. What actually rescues real implementations is that random and planar graphs have small diameters whichever order is used, not that the order was chosen well.

Two passes is not the general answer either. On the sparse random graphs the algorithm takes 7 passes rather than 2, because the diameter is around $\log V$ and the sweep order is unrelated to any path. Between 2 and $V-1$ there is a whole range, and where a given run lands depends on the graph, the numbering and the sweep direction together.

There is a real algorithm hiding in the first observation. Shortest-path faster algorithm — SPFA — keeps a queue of vertices whose distance has changed and relaxes only their outgoing edges, which is Bellman–Ford with the sweep order chosen adaptively rather than fixed. Its worst case is still $O(VE)$ and its typical behaviour is much better, and the improvement is entirely in the quantity this section is about.

The other half of the trade #

If Bellman–Ford’s cost is overstated by two orders of magnitude, why use Dijkstra at all?

Because the precondition is not a formality. Here is the entire counterexample:

Four vertices, four arcs, one negative, and no negative cycle anywhere. The true distances from vertex 0 are 0, 2, 5, 3 — the route to vertex 1 goes the long way round, $0 \to 2 \to 1$, costing $5 - 3 = 2$.

Dijkstra returns 0, 4, 5, 5. Wrong at two of the four vertices, by 2 and by 2.

The failure is not an implementation slip and cannot be patched. Dijkstra’s correctness rests on a single idea: once a vertex has been popped with the smallest tentative distance, that distance is final, because every remaining route to it goes through some vertex with a larger tentative distance and edges only add. A negative arc destroys the last clause. Vertex 1 is settled at 4 before vertex 2 is examined at all, and by the time the $-3$ arc is relaxed the answer has been committed.

Two things are worth taking from how small that graph is.

A precondition that fails on four vertices is not an edge case. It is not something that “usually works” and occasionally does not. There is no size below which the algorithm is safe and no probability argument to fall back on.

The failure is silent. Nothing throws. Nothing loops. The algorithm terminates promptly and returns numbers that look exactly like distances. This is the same failure mode as a sort that leaves one element misplaced, and it is the reason this site’s gate cross-checks the three shortest-path algorithms against each other rather than testing each alone.

So the assertion that guards this is two-sided. Dijkstra must get the wrong answer on that graph, and Bellman–Ford must get the right one. If the first ever stopped happening, the counterexample would have stopped being one and every sentence in this section would need rewriting; if the second ever stopped happening, the comparison would be between two broken things.

The same counts, three ways #

The comparison this page makes is a comparison of classes, and a class is a claim about a sweep — so the sweep is taken again on a different regime and on narrower sets of algorithms.

The third reading narrows differently: not to the two algorithms the precondition separates, but to the two implementations of the one that has it, where the precondition is held fixed and something else moves.

Negative weights are not exotic #

The usual reaction to a negative-weight example is that real edge weights are distances and distances are positive. Shortest-path algorithms are used on plenty of graphs where the weight is not a distance.

Currency conversion. Take logarithms of exchange rates and an arbitrage opportunity is a negative cycle. The entire application is about detecting one, and Bellman–Ford detects negative cycles as a by-product — run one more pass than the bound allows, and anything that still improves is on a cycle of negative total weight. Dijkstra cannot express the question.

Anything with a rebate. A route with a toll and a subsidy, a schedule with a penalty and a bonus, a pipeline stage that recovers resources. Mixed-sign weights arise whenever the weight is a cost in the accounting sense rather than a length.

Reductions. Difference constraints — systems of inequalities of the form $x_j - x_i \le c$ — are solved by shortest paths on a graph whose arcs are the constraints, and there is no reason for $c$ to be positive. This is how a scheduler decides whether a set of timing requirements is satisfiable at all, and the negative cycle is the proof of infeasibility.

In every one of those, “use Dijkstra, it’s faster” is not a performance decision. It is a wrong answer.

The relaxations that change nothing #

There is one more measurement worth making, because it explains why the early exit helps as much as it does.

The counted graph tracks relaxation attempts and relaxation improvements separately. On a sparse graph of 2,048 vertices, Bellman–Ford performs 86,016 attempts across its seven passes. The improvements are concentrated almost entirely in the first two: by pass four the algorithm is walking every edge in the graph to discover that nothing has changed, and it does that three more times before it is allowed to stop.

Pass by pass, on that graph:

The improvements fall by roughly a factor of three per pass. Eighty-seven percent of them happen in the first two passes; the sixth pass improves three distances out of 12,288 attempts, and the seventh exists only to establish that the sixth was the last. Across the whole run there are 8,635 improvements against 86,016 attempts, so ninety percent of the algorithm’s work changes nothing.

That is why the exit condition is not merely an optimisation but the thing that makes the algorithm usable, and it is also why the bound and the behaviour diverge so far. The bound counts attempts, the useful work is improvements, and the ratio between them is a property of how quickly distance information propagates — which is a property of the graph’s diameter, which appears nowhere in $O(VE)$.

An algorithm whose published cost counts a quantity that is mostly wasted is not unusual. What is unusual is being able to say how much is wasted, on stated graphs, exactly.

The class the algorithm does fit #

Saying that the algorithm carries no declared class is accurate and it is not the end of the story, because there is a class it fits exactly, and the reason it is not the published one is instructive.

Let $d$ be the number of passes the early exit takes — which the measurements identify as the hop-eccentricity of the source, the largest number of edges on any shortest path leaving it. Then the algorithm performs exactly $d$ sweeps of $E$ edges, so its attempts are $dE$, precisely and by construction. On the sparse graph of 2,048 vertices that is $7 \times 12{,}288 = 86{,}016$, which is the attempt count the pass table sums to.

That is a fit with no residual at all, and it is a fit to a bound with a second parameter in it. $O(VE)$ is that bound with $d$ replaced by its largest possible value, and $d = V-1$ requires a graph and a sweep order conspiring in the way the reversed path does. Everywhere else the substitution throws away the parameter that decides the answer.

This collection has a name for that shape and a measurement of it in another field. A band as wide as the answer is the same construction — a cost stated in a quantity the input possesses rather than in the input’s size — and it behaves the same way: enormously better than the size-only bound on ordinary inputs, identical to it in the worst case, and useless as a planning figure because the parameter is not known until the algorithm has run.

Three consequences worth separating.

The parameterised bound is provable, not fitted. $d$ passes of $E$ relaxations is a count, not a regression, so nothing here is a claim that a curve looked straight. What was measured is $d$, which is a property of each graph, and the product then follows.

It restores the comparison with Dijkstra to something meaningful. $dE$ against $E\log V$ is a comparison between $d$ and $\log V$, both of which are small on ordinary graphs and neither of which is $V$. At 2,048 vertices $d$ is 7 and $\log_2 V$ is 11, which is the right order for the measured factor of three once the queue operations are priced in.

And it names what a practitioner would have to know. Sizing a run of this algorithm needs an estimate of the source’s hop-eccentricity, which for a random sparse graph is about $\log V$, for a grid is about $\sqrt V$, and for an adversarial numbering of a path is $V-1$. That is a much more useful question to be asked than “how many vertices”, and no statement of the published bound prompts it.

The trade is not binary #

The essay has set the two algorithms against each other as a choice, which is how they are always presented, and there is a third option that dissolves the choice for the case that matters most.

Reweighting. Add a vertex connected to every other by an arc of weight zero, run Bellman–Ford once from it to obtain a value $h(v)$ at each vertex, and replace every arc’s weight by $w(u,v) + h(u) - h(v)$. The triangle inequality on $h$ guarantees every new weight is non-negative; the telescoping of the $h$ terms along any path guarantees that shortest paths are unchanged. Dijkstra then runs correctly on a graph that had negative arcs, and the original distances are recovered by undoing the shift.

The precondition has moved rather than vanished, which is the honest way to describe it. Reweighting requires that no negative cycle exists — the potentials are otherwise undefined, and the Bellman–Ford pass that computes them is exactly the thing that detects the failure. So the construction inherits the general algorithm’s ability to answer the arbitrage question and hands the routing work to the fast one.

Whether it is worth doing is a matter of how many sources are asked about. For a single source it buys nothing at all: the Bellman–Ford run that produces the potentials has already produced the distances, and running Dijkstra afterwards is work for its own sake. For every source in turn it is the whole difference between $V$ runs of the general algorithm and one run plus $V$ runs of the fast one, which is the classical all-pairs construction and is why it exists.

So the sentence “use Dijkstra unless there are negative weights” is wrong twice over. The cost of not using it is a factor of three rather than two hundred, and the presence of negative weights does not by itself exclude it — it excludes running it directly on the weights as given.

What the pair is actually offering #

Rewriting the trade with the measurements in it:

The generality costs a factor of three on these graphs, not a factor of two hundred, and it buys correctness on a class of problems the faster algorithm cannot represent.

Which is a much better trade than the classes suggest, and nobody would know it from the classes. That is the whole of what measurement is for on this site: it cannot establish an asymptotic claim, and it can show that the asymptotic claim, correctly derived and correctly quoted, describes something two orders of magnitude away from what the program does.