196. Longest Path in a DAG

Why this mechanism works

Topological order ensures every predecessor contributes before a vertex is used to extend a path. Store the best weight of a path ending at each vertex. Initializing every value to zero allows a path to start anywhere and prevents a negative prefix from being forced into a later path. Unit weights specialize this to unweighted path length in edges.

State and boundaries

best[v] is the largest known weight ending at v. When v is processed in topological order, all incoming alternatives have already been considered.

Protocol

1. Build weighted and unweighted adjacency.
2. Obtain a full topological order or reject a cycle.
3. Initialize all best values to zero.
4. For each ordered u, relax every edge with best[u]+weight.
5. Return the maximum, defaulting to zero.

Visualization

0 --(-5)--> 1 --(7)--> 2
best initially [0,0,0]
best[1] remains 0; best[2] becomes 7
optimal path starts at 1, avoiding the negative prefix

Python implementation

from kata_193 import topological_order

def longest_dag_path(n, edges):
    adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
    for u, v, weight in edges:
        adj[u].append(v)
        weighted[u].append((v, weight))
    order = topological_order(adj)
    if len(order) != n:
        raise ValueError('graph must be acyclic')
    best = [0] * n
    for u in order:
        for v, weight in weighted[u]:
            best[v] = max(best[v], best[u] + weight)
    return max(best, default=0)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=3; edges=[(0, 1, -5), (1, 2, 7)]; _=0

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=3; edges=[(0, 1, -5), (1, 2, 7)]; _=1

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=3; edges=[(0, 1, -5), (1, 2, 7)]; _=2

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=3; edges=[(0, 1, -5), (1, 2, 7)]; _=0

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=3; edges=[(0, 1, -5), (1, 2, 7)]; _=1

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=3; edges=[(0, 1, -5), (1, 2, 7)]; _=2

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=3; edges=[(0, 1, -5), (1, 2, 7)]; adj=[[], [], []]; weighted=[[], [], []]

L5 longest_dag_path: for u, v, weight in edges:
n=3; edges=[(0, 1, -5), (1, 2, 7)]; adj=[[], [], []]; weighted=[[], [], []]; u=0; v=1; weight=-5

... 9 intermediate state changes omitted ...

L12 longest_dag_path: for u in order:
n=3; edges=[(0, 1, -5), (1, 2, 7)]; adj=[[1], [2], []]; weighted=[[(..., ...)], [(..., ...)], []]; u=1; v=1; weight=-5; order=[0, 1, 2]; best=[0, 0, 0]

L13 longest_dag_path: for v, weight in weighted[u]:
n=3; edges=[(0, 1, -5), (1, 2, 7)]; adj=[[1], [2], []]; weighted=[[(..., ...)], [(..., ...)], []]; u=1; v=2; weight=7; order=[0, 1, 2]; best=[0, 0, 0]

L14 longest_dag_path: best[v] = max(best[v], best[u] + weight)
n=3; edges=[(0, 1, -5), (1, 2, 7)]; adj=[[1], [2], []]; weighted=[[(..., ...)], [(..., ...)], []]; u=1; v=2; weight=7; order=[0, 1, 2]; best=[0, 0, 7]

L12 longest_dag_path: for u in order:
n=3; edges=[(0, 1, -5), (1, 2, 7)]; adj=[[1], [2], []]; weighted=[[(..., ...)], [(..., ...)], []]; u=2; v=2; weight=7; order=[0, 1, 2]; best=[0, 0, 7]

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=4; edges=[(0, 1, 1), (1, 2, 1), (0, 3, 1)]; _=0

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=4; edges=[(0, 1, 1), (1, 2, 1), (0, 3, 1)]; _=1

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=4; edges=[(0, 1, 1), (1, 2, 1), (0, 3, 1)]; _=2

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=4; edges=[(0, 1, 1), (1, 2, 1), (0, 3, 1)]; _=3

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=4; edges=[(0, 1, 1), (1, 2, 1), (0, 3, 1)]; _=0

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=4; edges=[(0, 1, 1), (1, 2, 1), (0, 3, 1)]; _=1

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=4; edges=[(0, 1, 1), (1, 2, 1), (0, 3, 1)]; _=2

L4 longest_dag_path: adj, weighted = [[] for _ in range(n)], [[] for _ in range(n)]
n=4; edges=[(0, 1, 1), (1, 2, 1), (0, 3, 1)]; _=3

... 17 intermediate state changes omitted ...

L13 longest_dag_path: for v, weight in weighted[u]:
n=4; edges=[(0, 1, 1), (1, 2, 1), (0, 3, 1)]; adj=[[1, 3], [2], [], []]; weighted=[[(..., ...), (..., ...)], [(..., ...)], [], []]; u=1; v=2; weight=1; order=[0, 1, 3, 2]; best=[0, 1, 0, 1]

L14 longest_dag_path: best[v] = max(best[v], best[u] + weight)
n=4; edges=[(0, 1, 1), (1, 2, 1), (0, 3, 1)]; adj=[[1, 3], [2], [], []]; weighted=[[(..., ...), (..., ...)], [(..., ...)], [], []]; u=1; v=2; weight=1; order=[0, 1, 3, 2]; best=[0, 1, 2, 1]

L12 longest_dag_path: for u in order:
n=4; edges=[(0, 1, 1), (1, 2, 1), (0, 3, 1)]; adj=[[1, 3], [2], [], []]; weighted=[[(..., ...), (..., ...)], [(..., ...)], [], []]; u=3; v=2; weight=1; order=[0, 1, 3, 2]; best=[0, 1, 2, 1]

L12 longest_dag_path: for u in order:
n=4; edges=[(0, 1, 1), (1, 2, 1), (0, 3, 1)]; adj=[[1, 3], [2], [], []]; weighted=[[(..., ...), (..., ...)], [(..., ...)], [], []]; u=2; v=2; weight=1; order=[0, 1, 3, 2]; best=[0, 1, 2, 1]

Why the solution is correct

Any nonempty path ending at v extends a path ending at a predecessor u. The recurrence considers every such last edge after best[u] is final; zero also considers starting at v. Induction along topological order makes each result exact, and their maximum covers every endpoint.

Time and space

O(V+E) time and space. Negative edges are safe because acyclicity, rather than nonnegative weights, orders dependencies.

Common mistakes

Using a single-source initialization answers a different question. Processing vertices by numeric ID is not necessarily a topological order.

Reasoning card

Transfer exercise

Require a nonempty path, then revise the initialization and all-negative case explicitly.