Introduction

The phrase "fast algorithm" for counting acyclic paths needs one immediate clarification: the answer depends on the kind of directed graph you have. If the graph is a DAG, dynamic programming gives an efficient solution. If the graph has cycles and you want the exact number of simple directed paths, the problem becomes much harder in general.

Case 1: The Graph Is A DAG

A directed acyclic graph has no directed cycles, so every path is automatically acyclic. That makes counting paths much easier because you can process vertices in topological order.

Suppose you want to count the number of paths from a source node s to every other node. The recurrence is simple:

paths[v] += paths[u] for every edge from u to v

Initialize paths[s] = 1, then sweep through the graph in topological order.

1from collections import defaultdict, deque
2
3
4def topological_sort(graph):
5    indegree = defaultdict(int)
6    for u in graph:
7        indegree[u]
8        for v in graph[u]:
9            indegree[v] += 1
10
11    queue = deque([node for node, deg in indegree.items() if deg == 0])
12    order = []
13
14    while queue:
15        u = queue.popleft()
16        order.append(u)
17        for v in graph[u]:
18            indegree[v] -= 1
19            if indegree[v] == 0:
20                queue.append(v)
21
22    return order
23
24
25def count_paths_dag(graph, source):
26    order = topological_sort(graph)
27    paths = defaultdict(int)
28    paths[source] = 1
29
30    for u in order:
31        for v in graph[u]:
32            paths[v] += paths[u]
33
34    return dict(paths)
35
36
37graph = {
38    "A": ["B", "C"],
39    "B": ["D"],
40    "C": ["D"],
41    "D": []
42}
43
44print(count_paths_dag(graph, "A"))

For this DAG, the count to D is 2, corresponding to A -> B -> D and A -> C -> D.

Complexity In A DAG

Topological sort takes O(V + E), and the dynamic-programming sweep also takes O(V + E). So the full solution is linear in the size of the graph.

That is the fast algorithm most people are looking for, but it only works because the graph has no directed cycles.

Case 2: The Graph Has Cycles

If the graph contains cycles and you still want to count acyclic paths, you are really asking for the number of simple directed paths. That is much harder.

There is no general-purpose linear-time algorithm for exact counting on arbitrary directed graphs. In fact, the problem is computationally difficult in the general case, and the number of simple paths can itself be exponential.

So the right answer changes:

• for DAGs, use topological dynamic programming
• for general digraphs, expect exponential behavior or use restricted cases, approximations, or parameterized methods

Exact Counting In A General Digraph

If the graph is small, you can do depth-first search with a visited set.

1
2def count_simple_paths(graph, source, target, visited=None):
3    if visited is None:
4        visited = set()
5
6    if source == target:
7        return 1
8
9    visited.add(source)
10    total = 0
11
12    for neighbor in graph.get(source, []):
13        if neighbor not in visited:
14            total += count_simple_paths(graph, neighbor, target, visited)
15
16    visited.remove(source)
17    return total

This is exact, but it is not fast on large cyclic graphs. It explores many path combinations explicitly.

How To Choose The Right Approach

Ask these questions first:

• is the graph guaranteed to be a DAG
• do you need counts from one source or between all pairs
• do you need exact counting or only estimates
• how large can the graph get

If the graph is a DAG, the problem is pleasant. If not, the algorithmic complexity changes dramatically, and pretending otherwise leads to misleading advice.

Common Pitfalls

The biggest mistake is presenting the DAG dynamic-programming algorithm as if it solved the general directed-graph problem. It does not. Topological order does not exist when the graph has cycles.

Another issue is forgetting that "acyclic path" in a cyclic graph means a simple path with no repeated vertices. Counting those paths can explode combinatorially.

Developers also sometimes sum path counts blindly in graphs with cycles, which can lead to infinite path counts if they accidentally count cyclic walks instead of simple paths.

Finally, define the problem target clearly. Counting all acyclic paths in the entire graph is different from counting paths from one source to one destination.

Summary

• In a DAG, counting acyclic paths is efficient with topological order and dynamic programming.
• The DAG solution runs in O(V + E).
• In a general directed graph with cycles, exact counting of acyclic paths is much harder.
• Depth-first search with a visited set works only for small cyclic graphs.
• Always clarify whether the graph is a DAG before choosing the algorithm.