Given a directed acyclic graph, return every path from start to end.
allTrips(graph, start, end)
Input format: edges | start | end, edges as a,b pairs. Output each path's nodes
joined by -, paths separated by ;, in depth-first order.
edges a,b a,c b,d c,d, start a, end d // → "a-b-d;a-c-d"
edges a,b b,c, start a, end c // → "a-b-c"
edges a,b, start a, end z // → "" (no trips)
The task is enumerating every path, not finding or counting one. Whenever a problem asks for all sequences satisfying a condition, that's backtracking: build a candidate incrementally, explore forward while options remain, undo the last choice at a dead end or complete answer, try the next.
A path is itself a depth-first concept — one unbroken sequence of choices from start to end. DFS from the current node implicitly builds the path taken to get there.
Maintain a mutable path list. Visiting a node, append it:
After exploring a node's possibilities, remove it before returning. This undo step is what makes the shared path list usable across siblings — without it, the path would keep growing across unrelated branches.
Since the graph has no cycles, there's no infinite recursion risk — every path strictly progresses through the DAG's structure, eventually reaching the destination or running out of edges. Unlike general graph traversal, no visited set is needed within a single path; acyclicity already guarantees termination.
There's no shortcut around visiting every path explicitly, since all of them are requested — you can't compute this with a counting trick the way you could for just the number of paths. DFS-with-backtracking does exactly the necessary work: time proportional to the total length of all output paths, the best possible when the output itself is that large.
def all_trips(graph, start, end):
result = []
path = []
def dfs(node):
path.append(node)
if node == end:
result.append(list(path))
else:
for next_node in graph.get(node, []):
dfs(next_node)
path.pop()
dfs(start)
return result
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.