CODEWITHSUNDEEP
algorithmgraph-theorydirected-acyclic-graphs
Saiiiira
Saiiiira

Reputation: 221

Number of paths between two nodes in a DAG

I want to find number of paths between two nodes in a DAG. O(V^2) and O(V+E) are acceptable.

O(V+E) reminds me to somehow use BFS or DFS but I don't know how. Can somebody help?

Upvotes: 18

Views: 28266

Answers (4)

jwezorek
jwezorek

Reputation: 9525

You can count the paths through a digraph efficiently using either dynamic programming or a memoized recursive call. Personally I find recursion easier to think about than DP with a table and all that. Below is the recursive version.

To understand this implementation, note that the number of paths from s to t equals the sum, for all x, of the number of paths from x to t where x is a direct successor of s (as mentioned by @stalker in another answer). We implement that idea recursively and memoize the recursion.

Some C++ below:

#include <iostream>
#include <unordered_map>

namespace {

    using digraph = std::unordered_map<char, std::vector<char>>;
    using memoization_tbl = std::unordered_map<char, int>;

    int count_paths(memoization_tbl& memos, const digraph& dag, char s, char t) {
        if (s == t) {
            return 1;
        }

        if (memos.contains(s)) {
            return memos.at(s);
        }

        int sum = 0;
        for (auto x : dag.at(s)) {
            sum += count_paths(memos, dag, x, t);
        }

        memos[s] = sum;
        return sum;
    }

    int count_paths(const digraph& dag, char s, char t) {
        memoization_tbl memos;
        return count_paths(memos, dag, s, t);
    }

}

int main() {
    digraph dag;

    dag['a'] = { 'd', 'b' };
    dag['b'] = { 'c', 'd' };
    dag['c'] = { 'd', 'e' };
    dag['d'] = { 'e' };

    std::cout << "number of paths = " << count_paths(dag, 'a', 'e');

    return 0;
}

Upvotes: 0

Shivam
Shivam

Reputation: 89

This question has been asked elsewhere on SO, but nowhere has the simpler solution of using DFS + DP been mentioned; all solutions seem to use topological sorting. The simpler solution goes like this (paths from s to t):

Add a field to the vertex representation to hold an integer count. Initially, set vertex t’s count to 1 and other vertices’ count to 0. Start running DFS with s as the start vertex. When t is discovered, it should be immediately marked as finished (BLACK), without further processing starting from it. Subsequently, each time DFS finishes a vertex v, set v’s count to the sum of the counts of all vertices adjacent to v. When DFS finishes vertex s, stop and return the count computed for s. The time complexity of this solution is O(V+E).

Pseudo-code:

simple_path (s, t) 
    if (s == t) 
        return 1 
    else if (path_count != NULL)
        return path_count 
    else 
        path_count = 0
        for each node w ϵ adj[s] 
            do path_count = path_count + simple_path(w, t) 
        end 
    return path_count 
end

Upvotes: 4

stalker
stalker

Reputation: 1340

The number of distinct paths from node u to v is the sum of distinct paths from nodes x to v, where x is a direct descendant of u.

Store the number of paths to target node v for each node (temporary set to 0), go from v (here the value is 1) using opposite orientation and recompute this value for each node (sum the value of all descendants) until you reach u.

If you process the nodes in topological order (again opposite orientation) you are guaranteed that all direct descendants are already computed when you visit given node.

Hope it helps.

Upvotes: 13

Jeremiah Willcock
Jeremiah Willcock

Reputation: 30969

Do a topological sort of the DAG, then scan the vertices from the target backwards to the source. For each vertex v, keep a count of the number of paths from v to the target. When you get to the source, the value of that count is the answer. That is O(V+E).

Upvotes: 30

Related Questions