Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Directed acyclic graph — where it appears

A directed graph with no cycles, so its vertices can be listed in an order where every arc points forward. That order lets shortest paths be computed in one relaxation pass, negative arcs included, where a graph with cycles needs repeated passes or a queue.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

10010³10³10⁴10⁵10⁶10⁷Vcounted workTopological order, one passDijkstra, binary heapBellman–Ford, all passesV from 64 to 2048, directed, acyclicwork = scans + visits + relaxations + queue comparisons

The precondition that removes the queue

Dijkstra maintains a priority queue to discover which vertex is safe to finalise next, and on a directed acyclic graph 65% of its counted work goes into that queue. The order it is discovering is already known. Relaxing in topological order makes exactly one relaxation per arc — 1,536 arcs, 1,536 relaxations — with no queue at all, and negative weights are fine.

graphs · Graph 24816326410⁵10⁶components the graph is built fromcounted workcomponents firstBellman–Ford, early exitBellman–Ford, every passV = 1,024, negative arcs between componentsvertices relabelled at random

A graph is as hard as its largest cycle

Negative arcs rule out Dijkstra's algorithm and leave Bellman–Ford, which on a thousand vertices does three million units of work. Stopping it when a pass changes nothing brings that to 78,496. Finding the strongly connected components first and running it inside each one brings it to 38,549 — and to a quarter of the early-exit cost when the components are small, because every cycle lives inside one.

graphs · Graph

Named alongside it

The objects these essays reach for when they reach for this one.

Bellman–FordCounted primitiveNegative weightRelaxationShortest pathTopological sortComplexity classCondensationDijkstra's algorithmDirected graphEarly exitEvaluation order

All concepts