Motivation
A directed graph without cycles has a special processing order: every edge goes forward. Once vertices are in that order, a shortest-path algorithm can finish each vertex after all of its possible predecessors have been processed. Negative edge weights are allowed because no later edge can lead back and revise an earlier vertex.
This chapter proves both parts: how to obtain a topological order or detect a directed cycle, and why one pass of edge relaxations in that order finds shortest paths. A failed topological sort is a structural certificate that the one-pass algorithm's hypothesis does not hold.
Definitions
Definition 3.4.1
(Topological order and DAG)
Let be a finite directed graph with vertices and edges. A topological order is an ordering of all vertices such that every edge has before . A directed acyclic graph is abbreviated DAG. A self-loop is a directed cycle; parallel edges are allowed and are counted separately in indegrees.
Definition 3.4.2
(Kahn's algorithm)
Kahn's algorithm computes indegrees, puts every zero-indegree vertex in a queue, and repeatedly removes one queued vertex and outputs it. For every outgoing edge from that vertex it decreases the head's current indegree, adding the head to the queue when the count becomes zero. The counts refer to the subgraph induced by vertices not yet removed. If fewer than vertices are output, the algorithm reports a cycle.
Definition 3.4.3
(Source labels and relaxation)
For shortest paths, suppose each edge has a finite real weight and a source is specified. Initialize and every other label to . Process vertices in topological order; for each outgoing edge , replace by . Treat as .
Theorem 3.4.4
(Topological sorting and cycles)
A finite directed graph has a topological order exactly when it is acyclic. Kahn's algorithm outputs such an order on a DAG and reports a cycle otherwise.
Theorem 3.4.5
(Shortest paths in a DAG)
On a weighted DAG, the one-pass topological relaxation algorithm computes the shortest source-to-vertex distances, including for unreachable vertices, in time after the graph is represented by adjacency lists.
Proof: sources and the queue
Proof
(A DAG has a source, and Kahn's output is a topological order)
A finite nonempty DAG has a zero-indegree vertex. Otherwise start at any vertex and repeatedly follow an incoming edge backward. Because there are finitely many vertices, some vertex repeats, and the repeated part gives a directed cycle. Removing a zero-indegree vertex from a DAG leaves a DAG, so Kahn's queue cannot become empty while vertices remain in an acyclic graph.
When a vertex is removed, its current indegree is zero, so every predecessor has already been removed. Therefore every edge of a fully output graph points forward in the output order. Conversely, a graph containing a directed cycle cannot have a topological order: following its edges would require each cycle vertex to come before the next and eventually before itself.
Proof
(An early stop exposes a cycle)
If Kahn's algorithm stops early, the remaining subgraph is nonempty and every remaining vertex has positive indegree within it. Following incoming edges backward must repeat a vertex and exposes a directed cycle. Thus the early stop is correct. The unprocessed set can contain vertices outside the cycle; the proof guarantees that at least one cycle lies within it.
Proof: topological relaxation
Proof
(Topological relaxation computes shortest distances)
Every finite tentative label is the weight of an actual source-to-vertex path: initially only the empty path to has weight zero, and each relaxation appends one edge to a previously represented path. Thus no finite label is smaller than the true shortest-path distance.
Consider the vertices in topological order. Before a vertex is processed, every incoming neighbor has already been processed, so every incoming edge has already been relaxed. If is reachable and is not , take a shortest path to and let be its predecessor. A directed path in a DAG cannot repeat a vertex. Its prefix to is a shortest source-to- path; otherwise replacing that prefix by a shorter one would give a shorter path to . By induction, was correct when was processed, so the relaxation of made at most the shortest distance. The path-witness invariant gives the opposite inequality, hence equality.
For , the empty path has weight zero and no directed path can return to in a DAG. Vertices unreachable from never receive a finite path witness and remain at . Negative weights cause no difficulty in the induction: topological order, not a smallest-label rule, ensures every relevant predecessor is processed first.
Proof X-ray
Why one pass suffices
The induction runs along the topological order, not along the size of the distances. Acyclicity is used twice. It provides the order, so every edge into has been relaxed before is processed. It also makes every path simple, so a shortest path to exists and its prefix is again a shortest path to the predecessor. The invariant that every finite label is the weight of a real path gives at all times, where is the true distance. Relaxing the last edge of one shortest path, after its tail is final, gives . The signs of the weights enter neither inequality, which is why negative edges are harmless. Without acyclicity it is the order that disappears: on a cycle no vertex can be processed after all of its predecessors.
Time and reconstruction
Kahn's algorithm computes indegrees by scanning edges once. Each vertex is queued and removed at most once, and each edge is scanned once when its tail is removed. Its time and space are with adjacency lists. The relaxation pass also scans each vertex and edge once, giving total time including topological sorting.
On a strict improvement to , record and the edge as a predecessor. For a reachable , tracing predecessors moves backward in topological order and therefore terminates at . Reversing the recorded edges yields a shortest path. Retaining an existing predecessor on equal-cost ties avoids unnecessary changes; parallel edges should be identified separately if the exact edge sequence matters.
Worked examples
Worked example 3.4.6
(A negative edge is harmless)
Let edges be of weight two, of weight five, and of weight . In order , processing sets and . Processing improves to . The negative edge is allowed because the graph is acyclic.
Worked example 3.4.7
(A source that is not first)
If is an edge but is unreachable from , a topological order may place before . Its label remains , so relaxing its outgoing edges does not change . The source need not be the first vertex in a topological order.
Worked example 3.4.8
(A cycle blocks the order)
For edges , and , every vertex has positive indegree. Kahn's initial queue is empty and no vertex is output. The three edges form a directed cycle, so no topological order exists.
Worked example 3.4.9
(A zero-indegree tie)
For edges and , both and initially have indegree zero. Either may be removed first. Both and are valid topological orders; uniqueness is not required by the algorithm.
Common mistakes
Counterexample mode
Negative edges do not always require repeated passes
In the acyclic example, has weight , yet one topological pass finds the correct value . Dijkstra's nonnegative-weight requirement belongs to its smallest-label finalization proof; a DAG gives a different order that remains valid with negative edges.
Common mistake
(An early stop does not put every leftover vertex on a cycle)
An early stop in Kahn's algorithm proves that the remaining subgraph contains a cycle, not that every unprocessed vertex lies on one. A vertex downstream of a cycle may remain unprocessed without itself belonging to a cycle.
Counterexample mode
Relaxing in a non-topological order
Consider the claim that one pass of relaxations that visits every vertex once is correct on any DAG, whatever order is used. Take edges of weight , of weight , of weight and of weight , and process the vertices in the order . Processing gives and . Processing gives . Processing lowers to , but has already been processed, so stays . Processing changes nothing. The true distance is . The order places before its predecessor , so it is not topological. In the topological order the labels become , then , then . The repaired claim requires a topological order, so that every vertex is processed after all of its predecessors.
Common mistake
(The order depends on the edges, not on the weights)
A topological order is a property of the directed graph, not of its edge weights. Changing weights leaves the order valid, while adding a backward edge can create a cycle and invalidate it. For example, orders the path , but after adding the edge no order exists.
Extracting an explicit cycle after an early stop
If Kahn's queue becomes empty while vertices remain, choose one remaining incoming edge for each remaining vertex. This is possible because every remaining indegree is positive. Start at any remaining vertex and repeatedly follow the chosen incoming edge backward. Store the first position at which each vertex was seen. A repeat must occur within at most visits.
The repeated segment gives a directed cycle when read in the forward direction of the recorded edges. For example, backward traversal may visit using edges , and ; reading those edges forward gives . A self-loop is a cycle of length one. Finding one remaining incoming edge per vertex can be done by scanning the original edge list after the early stop, so the extraction still takes time.
A vertex downstream from a cycle illustrates why the entire unprocessed set is not a cycle certificate. Add edge to the cycle . No vertex has zero indegree initially, so all four remain. Vertex is not on a directed cycle if it has no outgoing edge, but the remaining subgraph contains the cycle on .
Longest paths in a DAG
The same topological order computes longest path weights in a DAG. Initialize and other labels to , then replace each head label by as outgoing edges are processed. Every finite label is a path weight, and the same predecessor induction proves optimality with the inequalities reversed. Unreachable vertices stay at as a sentinel.
A DAG has only finitely many directed paths, so a longest reachable path exists even when some edges have positive weight. This does not extend unchanged to arbitrary graphs: a reachable positive cycle that can reach a target permits walks of unbounded weight. If the problem asks for a longest simple path in a cyclic graph, forbidding repeated vertices changes the problem and the one-pass DAG proof does not apply.
For the edges of weight two, of weight five and of weight , the longest distance to is five, while the shortest is . The two algorithms use the same topological order but opposite update operations. An unreachable label must also use the correct sentinel: for minimization and for maximization.
Ties, multiple edges and arithmetic
A graph can have many topological orders. Any zero-indegree vertex may be chosen at each step, and the correctness proof applies to all choices. The resulting predecessor path may differ between orders if several shortest paths have equal weight, but every reported finite distance is the same optimum.
With parallel edges, indegree counts include each edge copy. Removing their common tail decrements the head once per copy, and relaxation examines each weight separately. Treating two copies as one indegree contribution while decrementing twice can make the queue bookkeeping incorrect. A self-loop prevents its vertex from reaching indegree zero and is correctly recognized as a cycle.
The linear-time claim assumes exact arithmetic and comparison on edge weights and labels. For finite-precision or arbitrary-precision weights, the cost and reliability of those operations depend on the representation. The graph-theoretic invariant is unchanged, but its numerical implementation needs its own analysis. In particular, a finite numeric sentinel must not overflow when an edge weight is added or be confused with a valid finite path value.
Summary
A DAG always has a zero-indegree vertex, so Kahn's algorithm repeatedly removes one and produces a topological order. In that order, all incoming relaxations reach a vertex before it is processed, giving linear-time shortest paths even with negative weights.
Exercises
Quick check
(Give a topological order for the edges and .)
Which vertices have indegree zero at the start?
Solution · Answer
Either or is valid. Both and start with indegree zero, and must come after both.
Quick check
(In the negative-edge example, compute the distance from to .)
Compare the direct edge with the path through .
Solution · Answer
The path has weight , smaller than the direct edge of weight five. The shortest distance is .
Quick check
(Why does a finite nonempty DAG have a vertex of indegree zero?)
Walk backward along incoming edges.
Solution · Answer
Otherwise every vertex has an incoming edge, and repeatedly following incoming edges backward from any vertex would, in a finite graph, eventually repeat a vertex. The repeated segment is a directed cycle, contradicting acyclicity.
Quick check
(Can every unprocessed vertex after Kahn's algorithm stops early be assumed to lie on a cycle?)
Think of a vertex that only receives an edge from a cycle.
Solution · Answer
No. A vertex downstream of a cycle can remain with positive indegree even if it is not on any cycle. The remaining subgraph is guaranteed only to contain at least one cycle.