Counting paths & reachability

Overview

Beyond 'is there a path?' comes 'how many paths?'. In a DAG the number of distinct routes from a vertex to a target is the sum of the route counts of its successors, with the target itself counting as one. Memoising that recurrence keeps it linear even though the number of paths can grow exponentially — so the count is stored in a long long.

Why it matters

Counting paths appears in reliability analysis, combinatorics on lattices, evaluating probabilities over DAGs, and dependency analysis. The companion question — can one source reach every vertex — is a basic coverage/closure check for schedulers and crawlers.

Core concepts

Path-count recurrence. paths(v) = 1 if v==dst, else Σ paths(u) over edges v→u.

Memoisation. Cache paths(v); each vertex is computed once, giving O(V+E).

Overflow. Counts double at each branch — use long long.

Reachability closure. can_reach_all = one DFS whose visited count equals n.

Why memoisation is essential. Without a cache, a vertex reachable by many routes is recomputed once per route, and the work becomes exponential in the graph's branching. With one, each vertex is solved exactly once and the cost drops to O(V+E) — the same overlapping-subproblems argument that motivates dynamic programming.

Syntax notes

#include <stdlib.h>

/* count distinct paths src -> dst in a DAG; memo seeded to -1 */
static long long cp(const int *adj, int n, int v, int dst, long long *memo) {
    if (v == dst) return 1;                 /* one path: the empty continuation */
    if (memo[v] >= 0) return memo[v];
    long long t = 0;
    for (int u = 0; u < n; u++)
        if (adj[v*n + u]) t += cp(adj, n, u, dst, memo);
    return memo[v] = t;
}

long long count_paths(const int *adj, int n, int src, int dst) {
    long long *memo = malloc((size_t)n * sizeof *memo);
    if (!memo) return -1;
    for (int i = 0; i < n; i++) memo[i] = -1;      /* 0 is a VALID answer, so -1 is the sentinel */
    long long r = cp(adj, n, src, dst, memo);
    free(memo);
    return r;
}

Key points:

• -1 sentinel, because 0 (no path) is a perfectly valid cached result.
• Terminates only because the graph is acyclic; a cycle makes the recursion infinite.
• long long — path counts double at every branch and overflow int quickly.

Lesson

Beyond does a path exist, we often need how many. In a DAG the number of paths from a vertex is the sum of the path counts of its successors — a memoized recurrence that stays linear (counts grow fast, so use long long). A companion question, whether one source can reach every vertex, is a single DFS whose visited-count must equal n.

Code examples

#include <stdio.h> static int n=4, adj[16]={ 0,1,1,0, 0,0,1,1, 0,0,0,1, 0,0,0,0 }; static long long memo[4]; static long long cp(int v,int dst){ if(v==dst) return 1; if(memo[v]>=0) return memo[v]; long long t=0; for(int u=0;u<n;u++) if(adj[v*n+u]) t+=cp(u,dst); return memo[v]=t; } int main(void){ for(int i=0;i<n;i++) memo[i]=-1; printf("paths 0 -> 3 = %lld\n", cp(0,3)); return 0; }

Line by line

Common mistakes

Recomputing sub-paths without memoisation (exponential blow-up). Using int and overflowing. Running the count on a graph with cycles (undefined / non-terminating). Treating directed reachability as undirected.

Debugging tips

Compiler errors and warnings:

• -Wmaybe-uninitialized if memo is malloced without the -1 fill loop.
• No warning for running it on a cyclic graph.

Runtime symptoms:

• Always returns 0. The memo was zero-initialised, so every lookup hits a phantom cached 0. Use -1.
• Hangs or overflows the stack. The graph has a cycle; path counting is only defined on a DAG. Run cycle detection first on untrusted input.
• Counts are far too small. You returned at the first path found instead of summing all successors — this counts existence, not multiplicity.
• Counts go negative. int overflow; paths grow exponentially, so use long long (and even that has limits).
• src == dst returns 0. The base case must return 1 — there is exactly one trivial path.
• reach-all reports false for a valid source. You compared the visited count against the wrong total, or forgot the source counts itself.

Technique: hand-count paths on a small diamond graph (two routes) and a chain (one route). Those two catch both the base case and the summing logic.

Memory safety

• Sentinel choice is the safety point here. 0 is a legitimate path count, so calloc makes unvisited states indistinguishable from computed zeros — the cache then returns wrong answers permanently.
• malloc without seeding is worse: reading indeterminate values to decide whether a state is cached is undefined behaviour.
• Acyclicity is an unchecked precondition. A cycle causes unbounded recursion — a stack-exhaustion crash driven entirely by input data.
• Recursion depth equals the longest path; deep DAGs need an iterative topological-order formulation.
• Overflow. Path counts can exceed even 64 bits on moderately sized DAGs; apply a modulus if the problem specifies one, and document the limit.
• Free on every path, and validate src/dst before indexing.

Real-world uses

Concrete uses: Counting distinct execution routes through a control-flow graph (used in test-coverage analysis), enumerating dependency resolution orders, reliability analysis over a network of components, counting lattice paths in combinatorics, and probability propagation over a DAG. The companion reach-all check answers coverage questions: can this build target reach every module, can this crawler seed reach every page.

Professional best practices:

Beginner:

• Use -1 for the memo sentinel whenever 0 is a valid answer.
• Return 1 at the destination — the trivial path counts.

Intermediate:

• Verify acyclicity before counting on untrusted graphs; the algorithm has no defence of its own.
• Process in topological order iteratively when depth is a concern — the recurrence is identical.
• Be explicit about overflow: either use a modulus or document the maximum graph size the count supports.

Practice tasks

1. (Beginner) Count DAG paths. Implement long long count_paths(const int *adj, int n, int src, int dst) with a -1 memo. Example: the demo DAG 0->3 -> 3. Concepts: sum over successors, sentinel choice.

2. (Beginner) Reach-all. Implement int can_reach_all(const int *adj, int n, int src). Concepts: DFS visited count equals n.

3. (Intermediate) Prove the sentinel matters. Switch the memo to calloc zeros and show the count collapses to 0. Concepts: why 0 cannot be the sentinel.

4. (Intermediate) Diamond and chain. Hand-count paths on a 4-vertex diamond (2) and a chain (1), and confirm your code agrees. Concepts: validating a counting recurrence.

Summary

In a DAG the number of paths from a vertex is the sum of the path counts of its successors, with the destination contributing 1 — a recurrence that memoisation turns from exponential into linear, since each vertex is computed once. The sentinel must be -1 rather than 0, because 0 (no path) is a valid cached answer and a zero-filled memo would return it forever. The algorithm terminates only because the graph is acyclic, so cycle-check untrusted input first, and use long long since counts double at every branch. The companion question — whether a source reaches every vertex — is a single DFS whose visited count must equal n.

Practice with these exercises

• Count paths in a DAG
• Can src reach every vertex?