The precondition that removes the queue

The bound with a precondition is about a clause at the end of a sentence. Dijkstra’s algorithm is correct provided no arc has a negative weight, and on a graph with one negative arc it returns a wrong answer at four vertices and says nothing. That essay is about what a precondition costs when it fails.

This one is about a precondition that pays. Impose acyclicity on the graph and the shortest-path problem loses its hardest part — not by making the algorithm cleverer, but by making one of its components unnecessary.

The distinction is worth having in a general form, because both kinds of precondition are written in the same place — a clause at the end of a theorem — and they do opposite things. A precondition that narrows the inputs and buys a guarantee is what Dijkstra’s non-negativity is. A precondition that narrows the inputs and removes a component is what acyclicity is here. Only the second changes the shape of the program rather than its correctness argument, and only the second is worth restructuring a problem to obtain.

What a priority queue is for #

Dijkstra’s algorithm works by finalising one vertex at a time, in increasing order of distance from the source. The correctness argument is that once the closest unfinalised vertex is picked, nothing can improve it — every remaining path to it goes through a vertex at least as far away, and with non-negative weights that path is at least as long.

So the queue exists to answer one question repeatedly: which unfinalised vertex is closest? That is the whole of its job, it is the only thing the algorithm cannot do in constant time, and the queue decides the class measured what choosing differently costs — 56,973 units of work against 2,118,656 on the same graph, depending on the structure used to answer it.

On an acyclic graph the question has already been answered. A topological order is an order in which every arc runs forwards, so a vertex’s predecessors all come before it, so by the time it is reached every path into it has been relaxed. It can be finalised on sight. There is nothing to decide, and the structure that exists to decide it has nothing to do.

Read the third row: 5,240 of Dijkstra’s 8,039 units of work are queue comparisons, and every one of them is deciding an order the graph already had.

There is a subtlety in the second row of that table that is worth flagging rather than glossing. Bellman–Ford with its early exit finishes on a DAG in two passes, and the reason is that the implementation sweeps vertices in index order — which on this generator’s graphs is a topological order, since every arc runs from a lower index to a higher one. So the row is measuring an algorithm that has stumbled into the right order rather than one that reasoned its way there, and on a DAG whose vertices were numbered adversarially it would take as many passes as the longest path is long. The measurement is of an implementation on a generator, and both halves of that matter, which is the standing caution of this whole field.

Exactly one relaxation per arc #

The claim that makes this rung worth measuring is not that the method is fast. It is that it is exactly the right number of operations, and the count is checkable to the unit.

A relaxation is an attempt to improve a tentative distance. Every arc affords one chance to improve the head’s distance from the tail’s, and a method that relaxes each arc once has taken every chance exactly once. At 512 vertices and 1,536 arcs the topological pass makes 1,536 relaxations. At 2,048 vertices and 6,144 arcs it makes 6,144.

Both directions of that equality matter and the gate holds both. Fewer would mean the order was wrong and some vertex was finalised before one of its predecessors — which produces a plausible distance array that is not the shortest-path array, and no exception. More would mean an arc was relaxed twice, which is the queue this method exists to avoid arriving by accident.

Bellman–Ford with the early exit makes 3,072 on the same graph — twice as many, because it cannot know it is finished until a pass changes nothing, and detecting that costs one more pass over every arc. That factor of two is the price of not being told the graph is acyclic, and it is a small price. The factor of 511 in the last row is the price of not being allowed the early exit either, which is the version the famous bound is about.

It is worth seeing the exactness as a kind of check rather than as a boast. Most counts in this collection are compared against a fitted curve, and a fit tolerates a constant factor and a bit of noise — a count that came out ten per cent high would fit just as well. An identity between two counted quantities has no tolerance at all: relaxations equal arcs, or the implementation is wrong. A claim with no tolerance in it is worth more than a claim with a fitted constant, and this field has exactly two of them: this one, and the requirement that a traversal visit every vertex of a connected graph.

The precondition is acyclicity, and it is not non-negativity #

The half of this that gets forgotten is which condition is doing the work.

Dijkstra needs non-negative weights. The topological method does not. Its correctness argument never mentions weights at all: it says that a vertex’s predecessors are processed before it, so every path into it has been considered, and that is true whatever the arcs cost.

The measured version of that is a graph whose arcs run from −4 to +5, on which the topological pass and Bellman–Ford agree at every vertex and 255 of 256 distances come out negative. Dijkstra on the same graph would be wrong, for the reason the earlier rung measured.

What a negative weight actually breaks is a shortest path’s existence, and only when there is a cycle: a negative cycle can be gone round repeatedly, so no shortest path exists and every method must either detect it or loop. An acyclic graph has no cycles at all, so the pathology cannot arise, and acyclicity is a stronger condition that includes what non-negativity was protecting against.

That is worth stating as a general shape. A precondition can be a restriction on the input that costs the caller something, and it can be a restriction that hands the algorithm information. Non-negativity is the first kind: it excludes graphs people have and buys a data structure. Acyclicity is the second: it excludes graphs people have and removes the need for one.

There is a second reading of that comparison worth taking, because it says something about how bounds get written. Dijkstra’s non-negativity precondition is famous; every statement of the algorithm carries it, and the bound with a precondition is about what happens when a reader ignores it. Acyclicity, by contrast, is usually mentioned as an aside — on a DAG this is easier — and the specific thing it buys is rarely stated as a count. Both are clauses about the input. One is treated as a warning and the other as a footnote, and the footnote is the one that removes a data structure.

What the topological order costs to have #

Nothing above is free and the accounting should say so.

Computing a topological order is itself a pass: count every vertex’s in-degree, which scans every adjacency once, then process the ready vertices, which scans every adjacency again. So the method spends three adjacency scans in total — one to count in-degrees, one to walk the order, one to relax — where Dijkstra spends one and Bellman–Ford with the early exit spends two.

That shows up in the table above as 4,608 edge scans against Dijkstra’s 1,536, and it is the reason the two algorithms’ total work is within a factor of 1.2 rather than a factor of four. The queue is not replaced by nothing; it is replaced by a counting pass, and the counting pass is cheaper because it is a sweep rather than a structure.

Two consequences follow.

The order is reusable and the queue is not. A topological order computed once serves every source vertex, every weight function and every subsequent query on the same graph. Dijkstra’s queue work is spent again on every run. On a graph that is queried repeatedly — a build dependency graph, a spreadsheet, a dataflow schedule — the counting pass is amortised to nothing.

And the order is the thing many callers actually wanted. A dependency graph is topologically sorted in order to be executed in that order; the shortest path is a secondary question asked of the same sequence. The pass was going to happen anyway.

One coincidence in the table above is worth naming before leaving it, because it is the best possible advertisement for reporting components rather than totals. The topological pass and the early-exit sweep have identical total work at five hundred and twelve vertices — 6,656 units each — and they are made of different things: the first spends three adjacency scans and one relaxation per arc, the second spends two of each, and the two sums are the same integer. A figure reporting one number per algorithm would have shown two bars of exactly equal length and said that the two methods cost the same, which is true in that unit and conceals everything interesting about either.

Where an acyclic graph comes from #

A precondition is only useful if inputs satisfying it turn up, and this one turns up constantly — often in problems nobody thinks of as graph problems.

A build system’s dependency graph is acyclic by definition; a cycle is an error the tool reports. A spreadsheet’s formula graph is the same. A version-control history is acyclic by construction, and the shortest path through it is what a merge-base computation is. A neural network’s forward pass, a dataflow schedule, a task graph with prerequisites, a course catalogue with requirements: all acyclic, all queried for longest or shortest paths, and all of them problems where the topological order was going to be computed regardless.

There is also a large class of graphs that are made acyclic on purpose. A general graph’s strongly connected components can be contracted to single vertices, and the result — the condensation — is always acyclic. So any problem that is invariant under contracting a component can be solved by contracting first and then using this method, which turns a general graph into a DAG at the cost of one component computation.

That last route is the reason the next rung is about components at all, and it is worth noticing that it makes the two rungs a pipeline rather than two topics: find the components, contract them, relax in topological order. Each step is linear, the composition is linear, and the whole of it is available on any directed graph whatever its cycles.

Why a dynamic program is this algorithm #

This field and the tables field have been describing the same thing from two directions, and it is worth joining them explicitly.

A distance that is a path through a grid says it from the other side: a dynamic program is a shortest-path computation on a graph whose topological order was free. The cells are vertices, the transitions are arcs, and the fill order is the topological order — which is why an edit-distance table needs no priority queue, why its cost is exactly the number of transitions, and why negative costs in a scoring matrix cause it no difficulty whatsoever.

Every result in the tables field is therefore an instance of this page’s method, and every result on this page is available there. The three fill orders of the same table, filled two ways are three topological orders of one dependency graph; the exactly-one-relaxation-per-arc property is the tables field’s transitions count; and the reason a table can be filled with no scheduling machinery is the reason this method needs none.

That is the sort of connection this collection exists to make, and it has a practical edge: a problem that can be posed as a dynamic program can be posed as a shortest path on a DAG, and the reverse. Which of the two framings is more useful is a matter of what else is wanted — the graph framing gives access to path counting and to bounds on partial paths, and the table framing gives access to the space and depth results the tables field measures.

What this rung adds to the field’s list of preconditions #

Three preconditions have now been measured in this field and it is worth setting them beside each other, because they behave differently and the differences are the useful part.

Non-negative weights, which Dijkstra needs. Violating it produces a wrong answer silently: four vertices out of a graph, no exception, no indication. The algorithm has no way to detect the violation without doing the work the precondition was meant to save.

Connectivity, which every traversal measurement here needs. Violating it produces an incomplete answer, and this field’s runner refuses it — a traversal that reached 480 of 512 vertices is not measured, because the counts from an incomplete traversal would still have fitted a convincing curve.

Acyclicity, which this page’s method needs. Violating it is detected for free, because the topological pass produces a short order and comparing its length to the vertex count is one comparison. The method refuses rather than answering.

Those three are the three possible outcomes and they are worth distinguishing by name: a precondition can fail silently, it can fail visibly in the output, or it can be checkable for nothing. Only the third is safe to leave unchecked in a library, and it is the only one of the three that is usually documented as an aside rather than a warning — which is exactly backwards.

What is not measured here #

Cycle detection is not charged. The method refuses a graph with a cycle by noticing that its topological order is short, which costs one comparison. What it does not do is find the cycle, which a caller usually wants and which costs another pass.

And the graph generator makes acyclicity structural. Every arc runs from a lower index to a higher one, so the graphs here are acyclic by construction rather than by inspection. That is deliberate — an essay about what a precondition buys should not be able to lose the precondition to a generator bug — and it means the measurements say nothing about how the method behaves on graphs that are nearly acyclic, which is the interesting practical case.

The graphs are sparse. Every measurement above is at a fixed average degree, and two parameters, one bound, no order is the standing reason that says nothing about the dense case. Dijkstra’s queue share in particular is a function of density: on a dense graph the adjacency scanning dominates and the queue’s 65% falls away, so the headline of this page is a headline about sparse acyclic graphs and not about acyclic graphs.

Nothing here is the longest path. The same recurrence with a maximum instead of a minimum gives the longest path, which is NP-hard on a general graph and linear here — a far larger difference than the one this page measures, arriving from the same precondition. It is not drawn because no algorithm on this site computes it.

Where this ladder goes next: two passes or one #

The method on this page relies on a traversal to produce an order. A traversal is also the thing that finds the components of a directed graph, and there the situation is the reverse of this one: two published algorithms with the same class, the same output and nothing in common, differing by a constant factor that nobody quotes.

Kosaraju’s method makes two depth-first passes and builds the transpose of the graph between them. Tarjan’s makes one and keeps a stack of low-link values. Both are $O(V + E)$, both are in every textbook, and the counted work differs by a factor of three on the same graph — because building a transpose reads every arc, which no statement of “two passes” mentions and which is the second pass’s real cost.

That is a comparison this field is equipped to make and has not, and it has the shape it likes: identical answers, identical classes, and a measured difference in the components of the work that the classes discard.