Given a directed acyclic graph as an adjacency list, return the number of distinct
paths from start to end.
possiblePaths(graph, start, end)
Input format: edges | start | end, edges as a,b pairs (directed a → b).
edges a,b a,c b,d c,d, start a, end d // → 2 (a→b→d, a→c→d)
edges a,b b,c, start a, end c // → 1
edges a,b, start a, end z // → 0
Counting paths between two nodes is another flavor of exhaustive exploration: the decision at each step is "which outgoing edge do I follow next?"
How many distinct paths lead from some node to the target? If the node is the target, there's exactly one path — the trivial path that goes nowhere, since you've already arrived. That's the base case.
Otherwise, the first step out must follow one of the current node's outgoing edges. Once committed, the rest is a path from that neighbor to the end — the same question, from a different node. So the count for the current node is the sum, over every neighbor, of paths from that neighbor to the end.
Every path leaves through some specific first edge — there's no other way out of a node. Grouping all paths by their first edge partitions them cleanly: each path belongs to exactly one group, and the remaining steps form a path from that neighbor to the end. Summing neighbor-counts counts every path exactly once.
This recursion has no visited-set bookkeeping — normally a red flag for graph traversal. If the graph had a cycle, a node could recurse back into itself and never terminate. Since it's guaranteed acyclic, following edges always progresses toward the end (or a dead end contributing 0), guaranteeing termination.
If many edges reconverge on shared downstream nodes (a "diamond" shape), the same downstream node gets recomputed independently for every path that reaches it — the recursion doesn't remember solving it before. Runtime ends up proportional to the number of paths, which can be exponential even in a small graph. Memoizing per node would convert this to linear time over nodes and edges, since there are only as many distinct subproblems as nodes — the logic doesn't change, only whether repeated subproblems get recomputed or looked up.
def possible_paths(graph, start, end):
if start == end:
return 1
total = 0
for nxt in graph.get(start, []):
total += possible_paths(graph, nxt, end)
return total
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.