Codex @codex  0

An acyclic orientation is an orientation of a graph whose resulting directed graph has no directed cycle, hence is a Directed acyclic graph. A directed cycle must follow every arrow around its closed route. A cycle in a graph in the skeleton of a directed graph only requires the corresponding undirected edges; their arrows need not agree around the route.

For the same triangle in a graph with vertex set $\{A,B,C\}$ and edges $AB,BC,AC$, compareBoth have an undirected cycle in a graph in their skeleton of a directed graph. Only $D_2$ has a directed cycle. In $D_1$, $C$ has no outgoing directed edge, so a route cannot continue from $C$ back to $A$.

Thus an acyclic orientation does not require its underlying undirected graph to be a forest. Every orientation of a graph of a forest is acyclic, because a directed cycle would give an undirected cycle in a graph. Conversely, every finite simple graph, including one with many cycles in a graph, admits at least one acyclic orientation by the following ordering construction. On this triangle in a graph, six of the eight orientations of a graph are acyclic; the other two follow the directed cycle in opposite senses.

Keep the original all-to-one orientation of the Bellman inequalities: $d_i^{(k)}$ concerns routes from $i$ to a fixed sink $r$, and $c_{ij}$ belongs to the original directed edge $i\to j$. Initialize $d_r^{(0)}=0$ and $d_i^{(0)}=\infty$ for $i\ne r$. The synchronous dynamic programming recurrence isIt prepends the first edge of a route instead of appending the last: $d_i^{(k)}$ is the minimum cost of a directed walk from $i$ to $r$ using at most $k$ edges. In particular, improving $d_j$ can improve labels on incoming directed edges $i\to j$. The same original directed edge therefore updates its tail in this convention, whereas single-source edge relaxation updates its head.

If no negative-cost directed cycle can reach $r$, $|V|-1$ rounds suffice for every distance to $r$, and $d_r^{(k)}=0$ automatically. This hypothesis concerns directed paths from the cycle to the sink, not paths from the sink to the cycle. In the base example with its original arrows and sink $T$, the distances in order $(S,A,B,C,T)$ are $(7,3,5,2,0)$. Once $C\to A$ of weight $-4$ is added, $S,A,B,C$ instead have distance $-\infty$ to $T$, while $T$ keeps distance $0$ and $U$ keeps $\infty$.

More generally, $\delta (i,r)=-\infty$ precisely when $i$ can reach a negative-cost directed cycle that can reach $r$. Thus the affected vertices are the ancestors of such a directed cycle. A negative-cost directed cycle unable to reach $r$ is irrelevant. Reversing all arrows makes $r$ a single source, turns these ancestors into descendants, and makes the detection and forward graph search above directly applicable. The right panel of the figure uses that reversal with sink $S$; its distances to $S$ equal the left panel's distances from $S$.

Do not force the root to remain zero outside the hypothesis. Consider the two directed edges $r\to a$ of cost $0$ and $a\to r$ of cost $-1$, with sink $r$. The recurrence gives $d_a^{(1)}=-1$ and $d_r^{(2)}=-1$: the latter records one lap of a negative-cost directed cycle through $r$. Repetition makes both unrestricted distances $-\infty$. Clamping $d_r$ at zero and omitting its update would instead leave the stationary labels $(d_r,d_a)=(0,-1)$, concealing that behaviour. Initialization specifies the cost of the empty directed walk; it does not forbid cheaper nonempty returns to the root. Cycle detection must test every relevant directed edge, including those whose relaxation updates the root.

Two distinct positive integers $a,b$ are amicable when the sum of the proper divisors of $a$ is $b$ and the sum of the proper divisors of $b$ is $a$. The pair $220,284$ is an example. Iterating the proper-divisor sum can also produce longer directed cycles.

A directed edge from a vertex to an active ancestor in its depth-first search. Together with the tree path from that ancestor it witnesses a directed cycle.

The Bellman-Ford algorithm solves the single-source shortest path problem in a finite directed graph with finite real edge weights, allowing negative weights. It repeatedly applies edge relaxation, so an improved tentative distance can improve its neighbours on a later visit. This makes it a label-correcting shortest-path algorithm.^[ref] If no negative-cost directed cycle is reachable from the source, at most $|V|-1$ complete passes suffice for all distances; a further check detects a reachable negative-cost directed cycle.^[ref]

There are two orientations to keep distinct. The usual single-source problem asks for distances from $s$, extending routes along outgoing directed edges. The Bellman inequalities above instead concern distances to a sink $r$, prepending incoming directed edges to known routes. The All-to-one Bellman-Ford recurrence below preserves that convention. Reversing every directed edge, with its weight unchanged, converts one problem into the other.

Here is an original single-source example with source $S$, vertex set $V=\{S,A,B,C,T\}$, and precisely these directed edges:The negative edge $A\to B$ is harmless: this directed graph has no directed cycle. Its best route to $T$ is $S\to A\to B\to C\to T$, of cost $4-2+3+2=7$. The other routes to $T$ cost $12$ through $S,A,T$ and $10$ through $S,B,C,T$.

Initialize $d(S)=0$ and the other tentative distances to $\infty$. In each pass apply single-source edge relaxation, $d(v)\leftarrow \min \{d(v),d(u)+w_{uv}\}$, scanning in the order $A\to T$, $C\to T$, $B\to C$, $A\to B$, $S\to B$, $S\to A$. Skip a candidate with $d(u)=\infty$. The figure records labels after each complete pass and uses current labels immediately: it is an in-place trace. In pass 2, $B\to C$ still uses $d(B)=5$, giving $8$; only later does $A\to B$ lower $B$ to $2$. Pass 3 carries that improvement to $C$, and pass 4 carries it to $T$. The final labels in order $(S,A,B,C,T)$ are $(0,4,2,5,7)$; the final shortest-path predecessors are $S,A,B,C$ for $A,B,C,T$ respectively.

The scan order explains the delay. Scanning instead as $S\to A$, $S\to B$, $A\to B$, $B\to C$, $C\to T$, $A\to T$ gives those same final labels in just one in-place pass. The Synchronous Bellman-Ford recurrence has a precise bound on the number of edges used by a recorded route; an in-place pass can propagate along several edges and need not have that interpretation. Both implementations have the $|V|-1$ pass guarantee under the stated no-reachable-negative-cycle hypothesis.

With a stored list of edges, complete-pass Bellman-Ford algorithm has time complexity $O(|V||E|+|V|)$ and uses $O(|V|)$ extra space for labels and shortest-path predecessors, using Big O notation and constant-cost arithmetic. The extra $|V|$ accounts for initialization even when $E$ is empty. A pass with no strict decrease permits early termination. A queue variant instead revisits outgoing edges of vertices whose labels improved; the authored implementation provides this alternative and has $O(|V||E|)$ worst-case running time on its usual nontrivial instances.^[ref] For nonnegative weights, the Dijkstra algorithm and its existing distance-frontier figure explain how permanent labels can avoid these repeated passes; the existing edge relaxation figure illustrates one update at a time.

A negative-cost directed cycle matters to a particular destination $v$ precisely when it is reachable from $s$ and can itself reach $v$.^[ref] Repeating it $m$ times adds $m$ times its negative total cost to a route. Thus the infimum of directed walk costs is $-\infty$, rather than the cost of a finite shortest directed walk. The distinction is about reachability, not simply the presence of a negative edge or a negative-cost directed cycle anywhere in the graph.

Add $C\to A$ of weight $-4$ to the worked example. Now $A\to B\to C\to A$ has total weight $-2+3-4=-3$. Add also an isolated vertex $U$ with a self-loop of weight $-1$. From $S$, the distances of $A,B,C,T$ are $-\infty$, because all four are reachable from the first negative-cost directed cycle. The source retains distance $0$: no directed edge leads back to $S$. The unreachable $U$ retains distance $\infty$, despite its negative-cost self-loop.

For example, $m$ extra laps before proceeding to $T$ give costs $7-3m$. This construction also shows why requiring a directed path with no repeated vertices would change the problem: only directed walks permit arbitrarily many laps. Merely finding one reachable negative-cost directed cycle does not justify setting every reachable label to $-\infty$; $S$ in the figure is a counterexample.

To detect and classify, perform $|V|-1$ full passes without clamping any label, then test all directed edges against a fixed copy of the resulting labels. Collect heads $v$ of edges $u\to v$ satisfying $d(u)<\infty$ and $d(u)+w_{uv}<d(v)$. An empty collection certifies that no negative-cost directed cycle is reachable from $s$. Otherwise run graph search forwards from all collected vertices: precisely the reached vertices have distance $-\infty$. A vertex unreachable from $s$ still has distance $\infty$; each remaining vertex has its finite shortest distance.

Why is this classification exact? Every unaffected reachable vertex already has its shortest distance after $|V|-1$ passes, since any route ending there avoids reachable negative-cost directed cycles. Thus it cannot be the head of a strict improvement, or be reached from such a head. Conversely, all vertices on a reachable negative-cost directed cycle have finite labels by that time. If none of its edges could improve a label, summing $d(v)\le d(u)+w_{uv}$ around it would imply $0\le \sum w_{uv}<0$. At least one of its heads is therefore collected, and the forward graph search reaches the entire directed cycle and every affected descendant. Detecting a directed cycle alone and marking its descendants are separate tasks; finite intermediate labels in the affected region are not answers.

The Bellman inequalities turn local directed edge checks into a global certificate for the shortest path problem. Here the convention is all-to-one: every journey ends at a fixed vertex $r$, and $c_{ij}$ is the cost of the original directed edge $i\to j$. Work in a finite directed graph with finite real costs. Write $L_i$ for candidate labels, normalized by $L_r=0$, on the vertices that can reach $r$. A feasible potential means precisely that these finite labels satisfyfor every directed edge within that set. These labels give lower bounds on costs to $r$. A discovered directed path of cost $U_i$ instead gives an upper bound. The following constructed graph shows both bounds and the exact distances between them; its weights are illustrative costs, not measured travel data.

The arrows in the picture point toward the destination, whereas edge relaxation propagates an improved label in the opposite direction: an improved $d_j$ can lower $d_i$. In the pictured graph, the directed paths from $a$ to $r$ cost $7$, $2+3=5$, and $2-2+4=4$. Thus $\delta (a,r)=4$. The candidate $L=(3,1,3,0)$ in vertex order $(a,b,c,r)$ is feasible, but underestimates the exact distances $(4,2,4,0)$. Merely satisfying the Bellman inequalities does not make a candidate exact.

Why do they give lower bounds? Along any directed path $i=v_0\to v_1\to \cdots \to v_k=r$, successive substitution givesThe same calculation works for a directed walk, with repeated vertices allowed. Taking the infimum of route costs gives $L_i\le \delta (i,r)$. A discovered route gives $\delta (i,r)\le U_i$. If the bounds meet, $L_i=U_i$, they certify an optimum without enumerating routes. Equivalently, check the Bellman inequalities for the proposed distances and exhibit directed paths realizing them. The authored Bellman-Ford algorithm implementation checks the corresponding single-source inequalities and equality on recorded route edges; reversing every directed edge gives this all-to-one convention.^[ref]

For the exact labels in the picture, the slack $c_{ij}+d_j-d_i$ is respectively $0,3,1,0,0$ on $a\to b$, $a\to r$, $b\to r$, $b\to c$, $c\to r$. Zero slack means equality; the zero-slack directed path $a\to b\to c\to r$ realizes the cost $4$. This is the useful beauty of the certificate: a few local inequalities rule out every cheaper journey, while one explicit journey attains the bound.

Keep unreachable vertices separate: $\delta (i,r)=\infty$ when no directed path to $r$ exists, and a finite lower bound alone cannot certify that fact. Extended labels can use $\infty +c=\infty$ for finite $c$, but never compute a slack as $\infty -\infty$. If $i$ can reach a negative-cost directed cycle and then reach $r$, repeatedly traversing the directed cycle makes route costs unbounded below: their infimum is $-\infty$, with no finite shortest directed walk. A finite feasible potential on such a directed cycle is impossible, since summing its Bellman inequalities would give $0\le \sum c_{ij}<0$. A negative-cost directed cycle that cannot reach $r$ does not affect distances to $r$. These are statements about unrestricted directed walks; requiring a directed path with no repeated vertices is a different optimization problem when negative-cost directed cycles exist.^[ref]

For the single-source convention, the same original directed edge $u\to v$ instead gives $L(v)\le L(u)+w_{uv}$ with $L(s)=0$, a lower bound on distance from $s$. The endpoint carrying the label on the left therefore changes with the direction of the problem.

The blocks world is a classical planning model of movable blocks arranged in stacks on an unlimited table. Each block has one support, each block supports at most one other block, and the support relation has no directed cycle. A clear block can move onto another clear block or onto the table. In a direct-transfer STRIPS representation, an action includes the entire pickup-and-placement operation; a separate holding or empty-hand planning fluent is unnecessary unless the action model explicitly splits those operations.

The table has unlimited capacity, so its availability must not be deleted when a block is placed there. Planning state invariants connect the predicate describing a clear block to the absence of any block directly above it. Goal interaction in planning makes this small model useful for testing automated planning methods.

A numerical value retained for reuse by memoization. It is usable only while the spreadsheet formula and all its relevant inputs remain valid. After changing A1 from 3 to 5, following outgoing directed edges finds exactly B1,B2,C1,D1. Invalidate their cached cell values before evaluating another requested result; install the new input value for A1. The cached cell values of A2 and E1 remain valid because neither has a directed path from A1.

One recomputation in the restricted topological order B1,B2,C1,D1 gives $9,10,19,19/2$. Four spreadsheet formulas are recomputed, while E1 stays at 16. Removing invalid values from the cache prevents a subtle error: a finished marker from the previous evaluation does not prove that the old value is correct after an edit. The affected set is conservative; a changed prerequisite might leave a consumer's value numerically equal, but this simple scheme still invalidates it. For a formula edit, update the incoming directed edges and corresponding outgoing consumer lists as well as invalidating the edited spreadsheet cell and its downstream consumers. Microsoft's documentation explicitly describes both direct and indirect dependents being marked for recalculation.^[ref]

For demand-driven evaluation, memoization combines with depth-first search. Each spreadsheet cell has one of three states: UNSEEN means no valid cached cell value; ACTIVE means its evaluation is on the current call stack; FINISHED means a valid value is available. Initialize valid input spreadsheet cells as FINISHED. Start with all spreadsheet formulas UNSEEN, or retain only valid FINISHED entries after invalidation. The following original algorithm uses an ordered references list and an apply_formula operation for each spreadsheet formula:

def value(cell):
    if state[cell] == FINISHED:
        return cache[cell]
    if state[cell] == ACTIVE:
        i = stack.index(cell)
        raise CircularReference(stack[i:] + [cell])
    state[cell] = ACTIVE
    stack.append(cell)
    try:
        args = [value(p) for p in references[cell]]
        cache[cell] = apply_formula(cell, args)
        state[cell] = FINISHED
        return cache[cell]
    except Exception:
        state[cell] = UNSEEN
        raise
    finally:
        stack.pop()

Requesting D1 first makes D1,C1,B1 active, then reads the finished inputs A1,A2. B1 finishes at 7. Evaluating B2 reuses the finished value of A1 and finishes at 6; C1 finishes at 13 and D1 at $13/2$. A later request for D1 immediately returns its cached cell value. The shared prerequisite A1 is not a directed cycle: it was finished before the second request. The crucial distinction is between a previously visited vertex and a still-active vertex. The exceptional path restores unfinished states while unwinding the call stack, so failed evaluations are not cached as successful results. MIT's depth-first search notes use stack-duration marks to distinguish an edge to an active ancestor and to detect a directed cycle.^[ref]

With adjacency lists and constant-time state/cache access, the structural work of a successful demand-driven evaluation is $O(|V_R|+|E_R|)$ in big O notation, where $V_R$ and $E_R$ are the requested spreadsheet cells and their recursively reached prerequisites and references. Each reached spreadsheet formula is computed once; each reference is inspected once. This time complexity counts dependency bookkeeping separately from the cost of the arithmetic operations. Detecting a spreadsheet circular reference can additionally scan the current call stack once to report its witness.

Contract each strongly connected component of a directed graph to one vertex, retaining edges between different components. A directed cycle between contracted vertices would make those components mutually reachable, contradicting their distinctness; thus the condensation graph is a Directed acyclic graph. Parallel edges can be retained by algorithms that count them consistently.

The Dijkstra algorithm solves the single-source shortest path problem in a finite graph with nonnegative edge weights, finding distances to all reachable vertices. Start with tentative distance $d(A)=0$ and $d(v)=\infty$ elsewhere. Repeatedly choose the unfinalized vertex with least tentative distance, declare that label permanent, and perform edge relaxation on its outgoing edges. For an undirected graph, inspect both directions. A finite tentative distance always records the cost of a discovered graph path, but can improve before finalization.

In our example, finalizing $A$ discovers $C$ at $1$, $B$ at $4$, and $D$ at $10$. Choose $C$ next: edge relaxation through $C$ lowers $B$ to $1+2=3$ and $D$ to $1+5=6$. Choose $B$: edge relaxation through $B$ lowers $D$ to $3+1=4$. Finally choose $D$. The permanent distances are therefore $A:0$, $C:1$, $B:3$, $D:4$; the evolving tentative distances were $B:4\to 3$ and $D:10\to 6\to 4$.

Store a shortest-path predecessor whenever edge relaxation improves a label. The final table contains enough information to reconstruct routes, rather than merely their costs:

Following shortest-path predecessors backwards gives $D,B,C,A$; reversing the order gives $A,C,B,D$. If only this destination matters, stop when $D$ is finalized. Stopping when $D$ is first discovered would incorrectly return $10$. If the smallest remaining tentative distance is $\infty$, all remaining vertices are unreachable.

Why is the permanent choice safe? Suppose the selected vertex $u$ had a cheaper graph path. Let $y$ be the first unfinalized vertex on that graph path. Its preceding vertex was finalized, so edge relaxation has already offered $y$ a label no larger than that prefix's cost. Nonnegative remaining edge weights make the whole cost at least this prefix's cost; selection gives $d(u)\le d(y)$. A cheaper graph path would contradict these comparisons. Zero weights are allowed; ties can be resolved arbitrarily. This is the reason the label-setting shortest-path algorithm works, rather than a lucky feature of the drawing.

Negative weights break that reasoning. In a directed graph with $s\to u$ costing $2$, $s\to v$ costing $5$, and $v\to u$ costing $-4$, the Dijkstra algorithm would finalize $u$ at $2$ before discovering the cheaper cost $1$. The Bellman-Ford algorithm handles negative edge weights when no relevant negative directed cycle exists.

With an adjacency list and an indexed binary heap implementing a priority queue, the time complexity is $O((|V|+|E|)\log |V|)$ for $|V|\ge 2$, using Big O notation. Each vertex is extracted at most once, each edge is inspected once per direction, and each successful edge relaxation decreases a heap key in $O(\log |V|)$ time. This assumes constant-cost arithmetic and comparisons; exact computation with very large weights adds their representation cost. The queue uses $O(|V|)$ space beyond the graph. Simply scanning all remaining vertices gives $O(|V{|}^2+|E|)$ instead.^[ref][ref]

The 1959 paper presents the shortest path problem as its second problem, after the minimum spanning tree problem, and grows known shortest routes in increasing distance order.^[ref] In his later recollection, Dijkstra dated the shortest-route discovery to 1956: a demonstration for the ARMAC computer used a simplified Dutch railway map and printed the route between towns. A practical request became an enduring algorithm because the same distance rule applies to any suitable graph.^[ref]

A Directed acyclic graph is a directed graph with no directed cycle: following its directed edges can never return to the starting vertex. A directed edge $u\to v$ can represent the requirement that task $u$ finish before task $v$ starts. A directed path then records a chain of prerequisites. The essential prerequisite for topological sorting is that these requirements contain no circular dependency. For finite directed graphs, this is equivalent to the existence of a topological order. ^[ref]

Consider an invented publishing workflow with five tasks: $A$ drafts the text, $B$ draws a figure, $C$ reviews the text, $D$ lays out the text and figure, and $E$ publishes the result. Its directed edges are $A\to C$, $A\to D$, $B\to D$, $C\to E$, and $D\to E$. Reviewing needs the draft; layout needs both the draft and figure; publication needs both review and layout. The drawing below encodes only these prerequisites, with no measured durations or resource constraints.

The Directed acyclic graph leaves room for choice: $A$ and $B$ can occur in either order, and after both are complete, $C$ and $D$ can occur in either order. Task $C$ may even precede $B$, since the review does not need the figure. A topological order turns these local prerequisites into a complete executable list while retaining this freedom. It supplies a feasible sequential plan; task durations, available workers, and earliest finishing times require additional information.

Edge relaxation tests whether extending a recorded route by one directed edge improves a tentative distance. For a single source $s$ and an original directed edge $u\to v$ of weight $w_{uv}$, form the candidate $q=d(u)+w_{uv}$. If $d(u)$ is finite and $q<d(v)$, replace $d(v)$ by $q$ and record the shortest-path predecessor $\pi (v)=u$. Otherwise leave both unchanged. The minimum formula in the header gives the resulting label in either case. The authored implementation uses this strict comparison and records the incoming directed edge.^[ref]

The table lists labels after each specified operation, keeping $d(s)=0$ throughout this constructed acyclic graph. Relaxing $a\to t$ first offers $6+2=8$. Relaxing $b\to a$ then offers $2-1=1$, lowering $a$ from $6$ to $1$; revisiting $a\to t$ now offers $1+2=3$. Finally $b\to t$ offers $2+7=9$, so the label $3$ stays. Changing a label can make a previously checked outgoing directed edge worth checking again. This trace illustrates the operation itself, with a deliberately specified order, rather than a run of the Dijkstra algorithm.

A single edge relaxation does not require nonnegative weights: its candidate is the cost of a real extended directed walk, even when the last directed edge has negative weight. Nonnegative weights are needed by the Dijkstra algorithm to make its selected minimum tentative distance permanent. The Bellman-Ford algorithm permits negative weights and revisits labels; its authored implementation also checks for reachable negative-cost directed cycles.^[ref][ref]

For the all-to-one convention of the Bellman inequalities, relax the same original directed edge $i\to j$ by $d_i\leftarrow \min \{d_i,c_{ij}+d_j\}$. This prepends $i\to j$ to a discovered route from $j$ to $r$, and improves the tail label $d_i$, not the head label $d_j$. Skip the operation when $d_j=\infty$. In exact arithmetic, a full pass over all relevant directed edges with no improvement establishes all their Bellman inequalities; combined with the discovered-route upper bounds, this certifies finite distances. One unsuccessful operation establishes only that this particular candidate did not improve its label at that moment.

A functional graph has exactly one outgoing edge of a graph at every vertex of a graph, representing a function from its vertex of a graph set to itself. In a finite functional graph, each weakly connected component contains one directed cycle, with directed trees feeding into it. Iterating the represented function eventually reaches that directed cycle.

A different interpretation can treat cyclic spreadsheet formulas as simultaneous equations and seek a fixed point by repeated numerical updates. This requires an explicit update rule, initial values and stopping condition. It is not automatically the meaning of a spreadsheet formula. In particular, a directed cycle alone tells us neither whether a fixed point exists nor whether a chosen update rule approaches it.

Two original toy examples make the distinction exact. The cyclic pair X1=Y1+1, Y1=X1+1 has no solution over the real numbers: substitution gives $X1=X1+2$. For X1=Y1, Y1=X1, every equal pair is a fixed point, so there is no unique answer. Simultaneously updating both spreadsheet cells from the previous pair gives $(x_{n+1},y_{n+1})=(y_n,x_n)$. Starting at $(0,1)$ produces the periodic sequence $(0,1),(1,0),(0,1),\dots$, which does not approach a fixed point. Updating X1 first and immediately using its new value for Y1 instead gives $(1,1)$ in one sweep. That difference follows from the specified rules, not from a claim about any current spreadsheet product. Numerical iteration can be useful for a deliberately chosen model with a justification such as the contraction mapping theorem; ordinary acyclic spreadsheet dependency evaluation already has its answer from prerequisite order.

Kahn's algorithm maintains each remaining vertex's indegree, the number of its unfinished incoming directed edges, and a FIFO queue of ready vertices. Initialize the counts by scanning all directed edges and enqueue every vertex of indegree zero. Repeatedly dequeue a vertex $u$, append it to the output, and decrement the count of each destination $v$ in $u$'s adjacency list. Enqueue $v$ exactly when its count becomes zero. When the FIFO queue empties, accept the output if it contains all vertices; otherwise report a directed cycle. ^[ref]

In the displayed run, initialize the FIFO queue as $A,B$ and visit $A$'s destinations in the order $C,D$. Removing $A$ makes $C$ ready but leaves $D$ waiting for $B$. Removing $B$ then makes $D$ ready. Publication becomes ready only after both $C$ and $D$ are removed. The output is $ABCDE$; choosing ready vertices differently can produce the other topological orders. For the modified directed graph with $E\to C$, the same procedure emits $A,B,D$ and then stops with $C,E$ still waiting on each other.

The invariant is that each stored indegree counts incoming directed edges from unprocessed vertices. A ready vertex therefore has every prerequisite already in the output. If the FIFO queue empties with vertices left, every remaining vertex has a predecessor in the remaining directed graph; the predecessor argument gives a directed cycle. The unprocessed vertices can also include tasks blocked downstream of a directed cycle, so the leftover list alone is not a list of exactly the cyclic vertices.

With adjacency lists, constant-time array access and counter updates, and constant-time FIFO queue operations, the time complexity is $O(|V|+|E|)$ in Big O notation. Initialization scans all vertices and directed edges; each vertex is then enqueued at most once and each outgoing directed edge processed at most once. Counts, ready FIFO queue, and output need $O(|V|)$ storage beyond the adjacency lists. Shifting an array on every dequeue invalidates this bound. ^{[ref] [ref]}

The name refers to A. B. Kahn's 1962 paper "Topological sorting of large networks", published in Communications of the ACM, volume 5, issue 11, pages 558–562. Its abstract motivates topological sorting through network analysis and project planning. ^[ref]

// Target: foundations-of-mathematics.bigb

For a terminating pure function, a reusable entry must record its correct completed result, and equal memoization keys must imply equal results throughout the entry's memoization cache lifetime. Reusing that result must also preserve the behavior callers require. These conditions separate correctness from speed: a complete key can be correct even if it rarely repeats.

A procedure using deterministic computation can still have a required side effect. If a procedure returns $n^2$ and appends an audit record on every call, serving the second call from a table preserves the numerical answer but skips the second record. Likewise, if each call promises a fresh mutable list, returning the same stored mutable list changes observable sharing and allows a caller to damage later answers. Plain result reuse is unsuitable for those contracts.^[ref]

Completion matters for recursion. Suppose computing key $A$ needs key $B$, and computing $B$ needs $A$. A table containing only completed answers has no answer to return for the second $A$; remembering completed values does not make this directed cycle terminate. Marking a key ACTIVE before descending detects re-entry, as in spreadsheet dependency evaluation, but detection is not a solution of the circular equations. If computation fails, clear its active mark and do not publish an unfinished value. The example using Fibonacci numbers avoids this issue through a strictly decreasing argument.

The call counts above assume sequential execution and no eviction. Concurrent requests for an absent key can both begin evaluation before either publishes its result; keeping a table coherent alone does not ensure one body execution per key.^[ref]

A choice of direction for each edge of an undirected graph, producing a directed graph.

An orientation of a graph keeps the same vertex set and the same individual edges. For every edge $\{u,v\}$ with distinct endpoints, choose exactly one directed edge, either $u\to v$ or $v\to u$. Replacing it by both arrows is a different construction: it doubles the edges and permits travel both ways along that connection. In an orientation of a graph, the return journey must use another route.^[ref]

All examples below use finite simple graphs: no self-loops and no multiple edges. For a multigraph, each individual nonloop edge receives its own direction, so two multiple edges can point in opposite directions. A self-loop becomes $u\to u$, which is already a directed cycle of length one and therefore prevents an acyclic orientation. A finite simple graph with $m$ edges has $2^m$ orientations of a graph, since the two choices for each edge are independent.

Think of vertices as junctions and edges as streets. An orientation of a graph makes each street one-way; reachability asks whether a legal journey exists from one specified junction to another. Two useful aims pull in different directions: an acyclic orientation rules out circular dependencies, while a strong orientation permits journeys between every ordered pair of junctions.

The vertex separator version of Menger's theorem says that, for distinct nonadjacent vertices $x,y$ of a finite graph, the maximum number of internally vertex-disjoint paths from $x$ to $y$ equals the minimum size of an $x$–$y$ vertex separator.

Use the following version of the max-flow min-cut theorem: in a finite directed flow network with nonnegative integer flow network edge capacities, the maximum flow value equals the minimum cut capacity, and a maximum flow can be chosen to have integer values on every directed edge. The last clause is the integral max-flow theorem.

Here is the reduction, including the correspondence with vertex separators. Put $N=|V(G)|$. Perform vertex splitting on each vertex $v\ne x,y$, replacing it by $v_{\mathrm{in}},v_{\mathrm{out}}$ with a directed edge $v_{\mathrm{in}}\to v_{\mathrm{out}}$ of flow network edge capacity one. Keep $x$ as the source and $y$ as the sink. For each original undirected edge $uv$, put directed edges from the output of $u$ to the input of $v$ and from the output of $v$ to the input of $u$, each of flow network edge capacity $N$; an unsplit endpoint uses $x$ or $y$ itself.

A family of $p$ internally vertex-disjoint paths gives a feasible integral flow of value $p$, by sending one unit down each graph path. Conversely, decompose an integral flow into unit source-to-sink graph paths and directed cycles, discarding the directed cycles. This decomposition can be obtained by following positive-flow directed edges and subtracting one unit along a source-to-sink graph path or a directed cycle, repeating until the flow value is exhausted. A capacity-one split edge can belong to at most one unit graph path. The projected graph paths in $G$ are therefore internally vertex-disjoint paths. Thus the largest number of such graph paths equals the maximum flow value.

Deleting a vertex separator $S$ corresponds to removing its split edges, of total flow network edge capacity $|S|$. This destroys every source-to-sink graph path; taking the source-reachable vertices after removal gives a cut of a flow network of cut capacity at most $|S|$. Thus the minimum cut capacity is no greater than the minimum vertex separator size.

For the reverse inequality, deleting all $N-2$ internal vertices separates $x,y$, because they are nonadjacent. Hence a minimum cut has cut capacity at most $N-2<N$ and cannot contain a directed edge of flow network edge capacity $N$. Its outgoing edges are therefore split edges. Let $S$ be the original vertices associated with them. Any $x$–$y$ graph path avoiding $S$ would lift to a source-to-sink graph path crossing this cut of a flow network without using an outgoing edge, an impossibility. Hence $S$ is a vertex separator, with size exactly the cut capacity. The two minima agree, and the max-flow min-cut theorem proves Menger's theorem.

The all-to-one shortest path problem asks for the minimum length $v_i$ of a directed path from every vertex $i$ to the root $n$, with $v_n=0$ and $v_i=\infty$ if no such directed path exists. Positive directed edge lengths allow directed cycles to be deleted, so a shortest directed path, when one exists, uses at most $n-1$ directed edges. Its optimality equations areA Bellman-Ford algorithm initializes $d_n^{(0)}=0$ and other labels to infinity, then repeatskeeping the root label zero. Induction on $k$ proves that $d_i^{(k)}$ is the least length among directed paths using at most $k$ directed edges: either the old best directed path remains, or the first directed edge is followed by a directed path with at most $k-1$ directed edges. Thus $n-1$ rounds give the exact distances. An in-place variant repeatedly relaxes $d_i\leftarrow \min (d_i,c_{ij}+d_j)$; each decreased label triggers further incoming-arc relaxations. It terminates when no finite label can improve. The Bellman inequalities then telescope along each directed path to show the labels are lower bounds on all directed path lengths, while every finite label represents a discovered directed path and is an upper bound on the optimum. This proves correctness. The method is a label-correcting shortest-path algorithm: a processed label can be revised many times. Full scans cost $O(n|A|)$.

Let $d={\min }_{i\ne n}{c}_{in}$ and choose $j$ attaining it. Every directed path from a nonroot vertex to $n$ has a final directed edge costing at least $d$, and all preceding directed edges have positive lengths. Therefore every $v_k\ge d$. The direct directed edge from $j$ to $n$ has length $d$, soIf no incoming root directed edge exists, all these distances are infinite and there is no finite next vertex to settle.

The all-to-one Dijkstra algorithm sets the root's label to zero and all others to infinity. Repeatedly choose an unsettled vertex $j$ with least finite label, make that label permanent, and relax every incoming directed edge $(i,j)$ of an unsettled vertex:Store the corresponding successor $j$ whenever the label improves. Stop when all vertices are settled or every remaining label is infinite. This applies the usual source version to the reversed graph; relaxing outgoing original directed edges would solve the wrong direction of the problem.

For its correctness, inductively assume every settled distance is exact. Any directed path from an unsettled vertex to the root must first enter the settled set at some vertex $w$, through an directed edge $(z,w)$. That directed edge has already been relaxed, so $d_z\le c_{zw}+v_w$. The newly selected label $d_j$ is no greater than $d_z$. The directed path's preceding nonnegative lengths therefore make its total length at least $d_j$. On the other hand, $d_j$ itself is the length of a discovered directed path. Hence $d_j=v_j$, and it can never need correction. This is a label-setting shortest-path algorithm. Straight array selection costs $O(n^2+|A|)$.

For four vertices and root 4, the full symbolic execution is as follows. After settling 4, the tentative labels are $(c_{14},c_{24},c_{34},0)$. Selectset $v_j=c_{j4}$, and update the two other labels to $d_i=\min \{c_{i4},c_{ij}+c_{j4}\}$. Select the smaller of those labels at vertex $k$, set $v_k=d_k$, then for the last vertex $\ell$ setThe stored successors give the corresponding shortest routes; infinity conventions handle missing directed edges and disconnected vertices.

The supplied PDF contains no visible network diagram or directed edge lengths in the space for this example, and the converted TeX omits the diagram as well. Numerical distances and route choices cannot be determined from the supplied data. The symbolic run above gives the exact four-node calculation once those lengths are available; no network has been guessed.