The queue decides the class, and the pseudocode does not name it

Dijkstra’s algorithm, as it appears in every textbook:

Set every distance to infinity except the source’s. While the queue is not empty, remove the vertex with the smallest tentative distance, and for each of its neighbours, if going via this vertex is shorter, update the neighbour’s distance.

Eleven lines. There is a priority queue in the middle of it and the pseudocode does not say which one, because “priority queue” is an interface and the algorithm is correct with any implementation of it.

The interface is the same. The costs are not remotely the same. On a random graph of 2,048 vertices and 6,144 edges:

A factor of thirty-seven between the first and the last, from a choice the algorithm’s statement does not contain. This essay is about that gap and about the two rows below the first, because the second and third rows differ from each other by another factor of one and a half, and that difference is one line of initialisation.

Why the queue is counted separately #

This site’s graph field reports four primitives — adjacency scans, visits, relaxations and queue comparisons — and sums them into a quantity called work. It would have been simpler to report one number. The reason for four is visible in the table above: the three rows share three of the four counts exactly.

Every one of these runs performs 12,288 adjacency scans, 6,144 relaxation attempts and 2,048 visits, because those are properties of the graph and of Dijkstra’s structure rather than of the queue. All of the difference is in the fourth column. A single total would have shown the difference and hidden where it came from; four columns show that the traversal is a constant and the queue is the variable.

This is the same reasoning as carrying comparisons and cache misses separately in the sorting field, applied one level down. A count that cannot be decomposed cannot answer why.

The decrease-key that hardly ever happens #

The binary heap’s queue comparison count is 36,493 on that graph. The bound says $O(E \log V)$, and $E \log V$ here is $6{,}144 \times 11 = 67{,}584$. The measurement is a little over half the bound, and the reason is a detail that the analysis is right to ignore and a practitioner is not.

A heap costs $\log V$ per operation, and the operations are: $V$ pushes, $V$ pops, and up to $E$ decrease-keys. The $E \log V$ term is entirely the decrease-keys — one per edge, in the worst case.

Measured, on that graph, there are 824 decrease-keys for 6,144 edges. Thirteen percent. A relaxation only triggers a decrease-key when it actually improves a distance, and by the time Dijkstra reaches most edges the far end already has a better route. The worst case assumes every edge improves something, which requires the edges to arrive in decreasing order of usefulness, which random weights do not arrange.

So the famous term is running at an eighth of its worst case, and what is left — $V$ pushes and $V$ pops, each costing $\log V$ — is $V \log V$. That is exactly what the fit reports: on the sparse sweep, $V \log V$ and $E \log V$ both fit at 1.21, and they are indistinguishable because $E \propto V$ on that sweep. On the grid, where the same collapse happens, the fit prefers $V \log V$ at 1.22 over $E \log V$ at 1.36.

The bound is an upper bound and it holds. What the measurement adds is that the term it is dominated by is not the term that dominates the run.

The line of code that changes the class #

The two array-queue rows differ by 705,258 units of work, and the difference between the two implementations is this:

• Lazy. Push a vertex the first time it is reached. The queue holds the frontier.
• Eager. Push every vertex at the start with distance infinity. The queue holds everything not yet settled.

Both are correct. Both appear in print. The eager form is the one Dijkstra’s original paper describes and the one the $\Theta(V^2)$ bound is derived from: $V$ pops, each scanning a queue that starts at $V$ and shrinks, giving $V^2/2$ comparisons exactly. The lazy form is what most people write, because it needs no initialisation pass and no sentinel distances.

On a random sparse graph the two are within a factor of 1.5, because the frontier of a random graph is a constant fraction of $V$ and the lazy queue is nearly as full as the eager one.

On a grid they are a factor of nineteen apart:

The grid’s frontier is a ring of about $\sqrt V$ vertices. $V$ pops of a $\sqrt V$ queue is $V^{3/2}$, and $2{,}070^{1.5}$ is about 94,000, which is the right order for the measured 98,709 comparisons. The eager version does not care what the frontier looks like — its queue is always everything left — so it pays $V^2/2 = 2{,}142{,}450$, and the measurement is 2,143,485.

Two implementations of one algorithm, one of them $\Theta(V^2)$ and one of them not, distinguished by whether a loop runs before the main loop.

What “which queue” is actually a question about #

Laid out as a decision, the choice of queue is three separate trades, and only one of them appears in the complexity table.

Per-operation cost against per-operation count. A heap costs $\log V$ per operation and an unordered array costs $1$ to insert and $V$ to extract. Since Dijkstra performs $V$ extractions and up to $E$ decrease-keys, the array is better when $V^2$ beats $E\log V$, which is a statement about density. This is the trade the table describes.

Whether decrease-key is supported at all. A binary heap can only do decrease-key in $\log V$ if it maintains an index from vertex to heap position — otherwise finding the entry is a linear scan and the bound is $O(EV)$, worse than the array. The index is easy to forget and the resulting implementation is still correct, so it is a silent factor of $V/\log V$. Many library heaps do not offer decrease-key at all, and the standard workaround is to push a duplicate entry and discard stale pops, which changes the queue size from $V$ to $E$ and the bound from $E \log V$ to $E \log E$ — the same to within a factor of two, and a different expression.

What the graph looks like. Not the density, which the table does mention, but the frontier, which nothing mentions. A planar graph and a random graph of the same $V$ and $E$ give the lazily-filled array queue two different complexity classes.

Only the first is in the analysis. The second is an implementation detail that changes the class. The third is a property of the input that changes the class. This is the same shape as the sorting field’s discovery that a complexity class without a named input distribution is a claim with a missing argument, and here there are two missing arguments rather than one.

The better queue nobody uses #

There is a third answer to “which queue”, and it has the best bound of the three and is almost never used. Understanding why is the most useful thing in this essay.

A Fibonacci heap supports decreaseKey in amortised $O(1)$ and pop in amortised $O(\log V)$, which turns Dijkstra’s bound from $O(E \log V)$ into $O(E + V\log V)$. On a sparse graph that is an improvement by a $\log V$ factor on the dominant term, and it is one of the celebrated results in data structures.

Almost nobody uses one. The usual explanation is that its constants are large, which is true and is not the whole story. The measurement above supplies the rest.

The Fibonacci heap improves the decrease-key term. On the graphs here, Dijkstra performs 824 decrease-keys against 6,144 edges — 13% of the worst case, because most relaxations do not improve anything. Of the binary heap’s 36,493 queue comparisons, the decrease-keys account for a small fraction; the pushes and pops account for most of it, and the Fibonacci heap does not improve pops at all — its pop is amortised $\log V$, the same as the binary heap’s, with a worse constant.

So the structure optimises a term that is an eighth of its worst case and leaves the dominant term alone, in exchange for a considerably worse constant on everything and a much larger node. The bound improves and the program does not.

That is a general shape worth naming, because it recurs whenever a data structure is chosen from a table of bounds:

A bound improved on a term that does not dominate is not an improvement. Deciding whether a term dominates needs a measurement, and the measurement needs a workload — so the choice of data structure cannot be made from the bounds alone, however carefully the bounds are compared.

The same argument disposes of the intermediate option in the other direction. A $d$-ary heap — four children per node instead of two — makes the tree shallower, so decreaseKey and the sift-up get cheaper by a factor of $\log d$, and pop gets more expensive because each sift-down step compares $d$ children instead of two. For Dijkstra, where decrease-keys outnumber pops, that is the right trade, and $d = 4$ is a common recommendation. It is a small improvement to the same term the Fibonacci heap targets, bought at almost no cost, which is why it survives where the asymptotically better structure does not.

Prim is the same loop, and inherits everything #

Prim’s algorithm for a minimum spanning tree differs from Dijkstra’s in one expression: the key stored for a vertex is the weight of the cheapest edge reaching it rather than the length of the cheapest path. Everything else — the pop, the scan, the conditional update — is identical.

So it inherits every property of this essay. It declares $E \log V$, the fit grants it on sparse graphs at 1.15 and on grids at 1.11, and refuses it on dense graphs at 1.86 for exactly the reason Dijkstra’s is refused: at $V = 512$ and half density, Prim spends 132,400 units scanning adjacencies and 3,599 in the queue. The queue is 1.8% of the work.

Kruskal, which reaches the same tree by a completely different route — sort every edge, then use union–find to reject the ones that close a cycle — has no class on this site at all, and its measurement is worth stating because it is a different kind of refusal:

Kruskal’s usual bound is $O(E \log E)$, from the sort, and the sort really is that. The total is not, over any range measured here, because three other terms — one adjacency scan per edge, one union–find query per edge, one visit per vertex — are all linear in $E$ and dilute the logarithm. Work ÷ $E$ is flat to 1.10 on the sparse sweep; work ÷ $E \log V$ varies by 1.67 and is refused.

That is a genuinely awkward result to report and it is the correct one. The published bound describes a component. The component is real, the bound on it is right, and the measured total over the sizes anybody draws is linear in $E$. Both facts are true and only one of them is ever stated.

The practical reading is the one the table gives: on sparse and planar graphs the two algorithms are within 15% of each other and the choice is about which is easier to write, and on dense graphs Prim is four times cheaper because Kruskal sorts $V^2/4$ edges of which it uses $V-1$.

The same decomposition, three ways #

The bars are where the work goes, and which bar dominates is the whole of “which queue” — so the decomposition is taken on the other regime and on two narrower sets.

The third set is chosen for the queues rather than for the algorithms: a plain FIFO, a binary heap, and no queue at all.

The general shape of the complaint #

An algorithm’s published complexity is a statement about an idea. An implementation is a specific thing, and between the idea and the thing there are usually two or three decisions that nobody records because they feel like details.

For Dijkstra there are three, and this essay has measured all of them: which queue, whether the queue is filled eagerly or lazily, and whether the heap maintains a position index. Each is invisible in the pseudocode. Each changes the complexity class in some regime. Together they span a factor of thirty-seven on one graph and a factor of nineteen on another.

The lesson is not that the analysis is wrong; it is right about the thing it describes. The lesson is that the thing it describes is not uniquely determined by the pseudocode, and that a bound quoted for “Dijkstra’s algorithm” is quoting a bound for one of several algorithms with that name.

This is why every measurement in this field names the implementation as well as the input, in the same breath and for the same reason. The foundation’s discipline was: name the input, name the range, and let the claim be refused. The graph field adds: name the density, and name the queue.

A fourth queue, if the weights are integers #

The three queues measured here are all comparison-based, and the whole $\log V$ in every bound above is the price of ordering by comparison. Drop that assumption and a fourth answer appears.

If the edge weights are integers bounded by $C$, then every tentative distance in the queue lies within $C$ of the smallest one — because a vertex is only in the queue if some settled vertex reaches it by one edge. So the queue can be an array of $C+1$ buckets, indexed by distance modulo $C+1$, with a cursor that advances as distances settle. Insertion is an array write, decrease-key is a removal and a write, and extraction is advancing the cursor to the next non-empty bucket.

The total is $O(E + VC)$ — no logarithm anywhere — and on a road network, where the weights are small integers in metres or seconds, that is a genuine improvement over every row of the table above rather than a rearrangement of constants.

It is not a better priority queue; it is a different model. The comparison-based bound of $\Omega(\log V)$ per extraction is a floor for structures that only compare keys, and a bucket queue escapes it the same way counting sort escapes the sorting floor — by using the keys as addresses. Both are the same move, and both stop working the moment the keys are real numbers or the range is large.

Which makes the choice of queue a four-way decision rather than a three-way one, with the fourth branch gated on a property of the weights rather than of the graph. That is a fourth missing argument to add to the three this essay has already found, and it is missing from the same sentence as the others.

What the duplicate-entry workaround costs in space #

The workaround named above — push a duplicate rather than decrease a key, and discard stale entries when they are popped — is what most implementations actually do, because most library heaps have no decrease-key. Its effect on the time bound is a factor of two inside a logarithm and is usually waved through.

Its effect on space is not a factor of two. A queue that never removes an entry until it is popped holds one entry per successful relaxation rather than one per vertex, so its size is bounded by $E$ rather than by $V$. On a dense graph that is a queue of sixty-six thousand entries where the indexed version holds five hundred.

Nothing in the complexity statement mentions it, and it is the difference between a queue that fits in cache and one that does not — which, given what this field has already measured about layout, is likely to cost more than the logarithm it was avoiding.

What to take from it #

Three implementation decisions, none of them in the pseudocode, each worth an order of magnitude somewhere: which queue, whether it is filled eagerly, and whether the heap keeps a position index. The published bound is correct about the algorithm it describes and does not identify which of the resulting programs that is.

The site’s response is to name the implementation alongside the input and the range, and to let the declaration be refused when the measurement disagrees. Two of the declarations in this essay were.