hardGraphsPure DSA~30 min
List Every Path From Source to Sink in a DAG
A directed acyclic workflow graph runs from stage 0 to the final stage n-1. Enumerate every distinct path from start to finish.
Problem
Given a directed acyclic graph of n nodes as graph where graph[i] lists the out-neighbors of node i, return all paths from node 0 to node n-1. Each path is the sequence of node indices visited.
Input
An adjacency list graph of out-edges for a DAG.
Output
A list of all source-to-sink paths.
Constraints
- 2 <= n <= 15
- graph is a DAG; node n-1 may be a sink.
- The number of paths can be exponential in n.
Examples
Example 1
Input
graph = [[1,2],[3],[3],[]]
Output
[[0,1,3],[0,2,3]]
Two distinct paths reach node 3.
Example 2
Input
graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output
[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
All five source-to-sink paths are listed.