An order makes dependencies safe
Let be a finite directed acyclic graph (DAG), represented by adjacency lists. For clarity assume no parallel edges; a path is specified by its ordered sequence of vertices. Choose a set of allowed starting vertices. A path of zero edges from each to itself counts as one path. We will count paths from any allowed start to each vertex and, with real edge weights, find the largest weight of such a path. An unreachable vertex has count zero and no finite maximum.
The topological-sort lesson proves that every edge in a DAG goes from an earlier vertex to a later one in any topological order. This is precisely what dynamic programming needs: when a vertex is processed, all paths arriving at it from predecessors have already contributed. Different valid orders need not give identical intermediate tables, but they give the same final answers.
Definition 5.5.1
(Path count and maximum path weight from allowed starts)
Let be the set of paths with , each an edge, and . The path count is . The maximum path weight is the largest value of over , where a zero-edge path has weight ; if is empty, and .
A useful order to inspect
For edges , , , the initial zero-indegree vertices are and . Either order of is valid; after both are removed, and then can be removed. For edges , , and isolated , removing and leaves the cycle and no zero-indegree vertex.
In the first component scenario, select then , or undo and select then . The displayed sequence changes, but both place after both of its predecessors. The component displays removal order and residual indegrees; it does not calculate path counts or edge weights. Those are worked out below. Its second scenario illustrates why a residual directed cycle invalidates the DAG prerequisite. The preceding paragraph supplies the same essential state in a static reading or export.
Count paths by their last edge
Initialize for and otherwise. Process vertices in topological order; when processing , for every outgoing edge perform
Theorem 5.5.2
(Counting by last edge)
Initialize for and otherwise, and process the vertices of a DAG in a topological order with the update above. Then for every vertex , and does not change after has been processed.
Proof
(Induction over the topological order)
Why does this count correctly? Every nonempty path ending at has a unique last edge , and removing that edge leaves a path ending at . Conversely, appending the edge gives a path ending at . These classes are disjoint because their last edges differ. The initial contributes the one zero-edge path when . Even if an allowed start has incoming paths from another allowed start, it receives those contributions in addition to its zero-edge path. By induction over the topological order, all and only the required contributions have arrived before is processed.
Proof X-ray
Where acyclicity, the zero-edge path and simple edges enter
The key move is the last-edge decomposition: it replaces a set of paths of unbounded length by a disjoint union indexed by the in-edges of , so one addition per edge suffices. The topological order makes the induction well founded. Every edge has earlier than , so by the time is processed each in-neighbor has already pushed its final count, and nothing can add to afterwards. Acyclicity is what guarantees that such an order exists, and it also makes finite, so is a number. The absence of parallel edges is used in the same step: two edges would give two different additions for one vertex sequence, which would disagree with the convention that a path is its vertex sequence. The initial value accounts for the only path with no last edge, and it is added to, never replaced, because a vertex of can also be the end of longer paths. The argument closes when the last vertex is processed, since every path ending at any vertex has by then been charged to exactly one last edge.
Maximum weight, including negative edges
Give each edge a finite real weight . Initialize for and otherwise. In topological order, for every with , perform
Theorem 5.5.3
(Maximum weight by last edge)
Initialize for and otherwise, and process the vertices of a DAG in a topological order with the update above, skipping edges whose tail has . Then for every vertex , for arbitrary finite real weights.
Proof
(The same induction for maximum weights)
The same last-edge induction proves that is the largest total weight of a path from an allowed start, with retained when no such path exists. For an allowed start the zero-edge path has weight zero; incoming paths can improve it. The finite DAG has only finitely many paths, so the maximum exists whenever is reachable. Negative weights cause no difficulty because a topological order processes every predecessor first and there are no directed cycles; this is not Dijkstra's algorithm.
Worked example 5.5.4
(Counts and weights on the first graph)
On the component's first graph, choose and weights , , . Either displayed order gives the following final values:
| Vertex | ||||
|---|---|---|---|---|
| 1 | 1 | 2 | 2 | |
| 0 | 0 | 2 | 5 |
There are two paths from the allowed starts to : and . Appending gives two paths to ; the maximum-weight one begins at and has weight . The zero-edge paths account for the counts at and . The component does not display this weight/count table; it displays the order used to compute it.
Worked example 5.5.5
(An allowed start with an incoming path)
Take , edges of weight and of weight , and the topological order . Initially and for . Processing along gives and . Processing along gives and . The paths to are the zero-edge path and the path , so ; the zero-edge path has weight and beats of weight . The paths to are (weight ) and (weight ), so and . This is the case in which an allowed start receives contributions in addition to its own zero-edge path.
Worked example 5.5.6
(The complete forward DAG on four vertices)
Take vertices , every edge with of weight , and , processed in the order . Then , , , and , one path for each subset of the interior vertices . For the weights, , , , : the longest path is with three edges, even though four paths exist. For the same formula gives , a single edge.
Concept lensAlgebraic
Counting as a triangular linear system
Let be the adjacency matrix, with for an edge , and let be the row vector with for and otherwise. Counting by the last edge says , that is, . In a topological order is strictly upper triangular, so is triangular with ones on the diagonal, and the update rule is exactly forward substitution: each is fixed by earlier entries. Equivalently , a finite sum, since once reaches the number of vertices. For the four vertices above, this gives .
Common mistake
(Starting every vertex with count one)
Only the allowed starts have a zero-edge path. With and the single edge , setting for every vertex would give , but the only path from to is . Initialize exactly when .
Common mistake
(Starting every maximum weight at zero)
Initializing for non-starts hides negative weights. With and the edge of weight , the true value is , but the update returns , a weight that no path attains. The same initialization would also make an unreachable vertex look reachable with weight . Use for non-starts and skip edges leaving a vertex whose value is .
Implementation and limits
First compute a topological order and check that it contains all vertices. If not, report that the DAG method is inapplicable; do not treat a partial order as a complete answer.
Counterexample mode
The recurrence on a graph with a directed cycle
Claim: the count recurrence also works on a graph with a directed cycle, if the vertices are processed in some fixed order. Take , edges , , , and the order . Initially and . Processing adds to . Processing adds to . Processing adds to , so the final table is , , . No reading of this table is correct. There are three simple paths from , namely , and , which would give counts ; counting walks instead gives infinitely many to and to (, , and so on). The value at includes the walk but its contribution was never passed on to . Every order leaves such an edge pointing backwards, because a directed cycle has no earliest vertex. A complete topological order exists exactly when the graph is acyclic, so the check that the order contains all vertices is a hypothesis of the method, not a formality.
Then initialize the arrays and scan each outgoing adjacency list once. This takes arithmetic operations and auxiliary array entries beyond the graph. Their storage in bits also grows with the encoded values. Store a predecessor when a maximum improves if an actual maximizing path is required; choose a tie convention if multiple paths attain the maximum.
The operation count assumes arithmetic on path counts takes constant time. Exact counts can be very large: in the simple DAG with vertices and every edge for , there are paths from to for , one for each subset of interior vertices. Exact integers therefore need a growing number of bits. Modular counts answer a different question, and fixed-width overflow can corrupt exact results.
Exercises
Quick check
(Let and edges of weight , of weight , and of weight ; is isolated. Give and for all four vertices.)
Solution · Answer
Counts are , , , . Maximum weights are , , , . The route through has weight and beats the direct edge of weight .
Quick check
(Why does initializing every allowed start with a count of one not assert that its count stays one?)
Solution · Answer
The initialization counts the zero-edge path. A path from another start can enter the vertex later in the dynamic program and contributes another path.
Quick check
(Why must the algorithm reject a partial Kahn order when vertices remain?)
Solution · Answer
A partial order does not process all vertices, so dependencies and outputs for the remainder have not been evaluated. With Kahn's algorithm the remaining graph contains a directed cycle; the finite-DAG proof does not apply.