188. All Paths from Source to Target in DAG

Why this mechanism works

This is path enumeration, so two routes may legitimately revisit the same graph vertex in different branches. A permanent visited set would remove valid answers after a merge point. The DAG guarantee prevents cycles within a route; a mutable path needs only append, recurse and pop.

State and boundaries

path is exactly the current valid route from zero to u. output contains independent copies of routes ending at the target.

Protocol

1. Handle the empty graph.
2. Start path with zero.
3. At the target save a copy and return.
4. For each outgoing neighbor append it, recurse and undo.

Visualization

0 -> 1 -> 3
 \-> 2 -> 3
3 belongs to two valid routes
output [0,1,3] and [0,2,3]

Python implementation

def all_dag_paths(adj):
    if not adj:
        return []
    output, path = [], [0]
    def visit(u):
        if u == len(adj) - 1:
            output.append(path.copy())
            return
        for v in adj[u]:
            path.append(v)
            visit(v)
            path.pop()
    visit(0)
    return output

Worked execution

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

L2 all_dag_paths: if not adj:
adj=[[1, 2], [3], [3], []]

L4 all_dag_paths: output, path = [], [0]
adj=[[1, 2], [3], [3], []]; output=[]; path=[0]

L6 visit: if u == len(adj) - 1:
u=0; adj=[[1, 2], [3], [3], []]; output=[]; path=[0]

L9 visit: for v in adj[u]:
u=0; adj=[[1, 2], [3], [3], []]; output=[]; path=[0]; v=1

L10 visit: path.append(v)
u=0; adj=[[1, 2], [3], [3], []]; output=[]; path=[0, 1]; v=1

L6 visit: if u == len(adj) - 1:
u=1; adj=[[1, 2], [3], [3], []]; output=[]; path=[0, 1]

L9 visit: for v in adj[u]:
u=1; adj=[[1, 2], [3], [3], []]; output=[]; path=[0, 1]; v=3

L10 visit: path.append(v)
u=1; adj=[[1, 2], [3], [3], []]; output=[]; path=[0, 1, 3]; v=3

... 14 intermediate state changes omitted ...

L12 visit: path.pop()
u=2; adj=[[1, 2], [3], [3], []]; output=[[0, 1, 3], [0, 2, 3]]; path=[0, 2]; v=3

L11 visit: visit(v)
u=0; adj=[[1, 2], [3], [3], []]; output=[[0, 1, 3], [0, 2, 3]]; path=[0, 2]; v=2

L12 visit: path.pop()
u=0; adj=[[1, 2], [3], [3], []]; output=[[0, 1, 3], [0, 2, 3]]; path=[0]; v=2

L13 all_dag_paths: visit(0)
adj=[[1, 2], [3], [3], []]; output=[[0, 1, 3], [0, 2, 3]]; path=[0]

L2 all_dag_paths: if not adj:
adj=[[]]

L4 all_dag_paths: output, path = [], [0]
adj=[[]]; output=[]; path=[0]

L6 visit: if u == len(adj) - 1:
u=0; adj=[[]]; output=[]; path=[0]

L7 visit: output.append(path.copy())
u=0; adj=[[]]; output=[[0]]; path=[0]

L13 all_dag_paths: visit(0)
adj=[[]]; output=[[0]]; path=[0]

Why the solution is correct

Every emitted sequence follows directed edges and ends at the target. Every source-to-target path determines a unique sequence of neighbor choices that is explored. No repeated edge entries duplicate that route, and acyclicity bounds every path length by n.

Time and space

Output-sensitive exponential worst case. A coarse bound is O(n*2^n) time/output for a simple DAG; O(n) auxiliary path and recursive depth.

Common mistakes

A global visited set incorrectly discards paths sharing a suffix. Removing the DAG precondition requires path-local cycle prevention and a clear definition of allowed paths.

Reasoning card

Transfer exercise

Count paths with reverse-topological dynamic programming when materializing every route is too expensive.