Count all possible paths between two vertices

Problem Statement

Given the directed, connected and unweighted graph G, and the task to find the number of all paths possible between two given vertices.

Note: The path does not contain any cycle which means path have finite number of vertices.

Example Input

Expected Output

4

Approach

The idea is to use backtracking. Traverse the path from the source node and check if path leads to destination node then increment the count and backtrack to other path.

Pseudocode

Count_Path_Recur(u, Destination, Check_Node_Visited, Path_Count):
    
    u <- make it visited
    
    if u is equal to Destination
        Path_Count[0] += 1
         
    otherwise 
        i = 0
        while i < len(Graph[u]): 
            if not Check_Node_Visited[Graph[u][i]]: 
                
                // Recursive calling
                Count_Path_Recur(Graph[u][i], Destination, Check_Node_Visited, Path_Count) 
                i += 1
    u <- make it unvisited

Implementation in Python

# Implementation
Graph = [] 
V= 0

def gragh_add(x):
    global Graph, V
    V=x
    Graph = [[] for i in range(V)] 

def addEdge(u, v): 
    # Add v to u’s list.
    global Graph
    Graph[u].append(v) 
    
# A recursive function to print all paths    
# from 'u' to 'd'. visited[] keeps track 
# of vertices in current path. path[] 
# stores actual vertices and path_index 
# is current index in path[] 
def countPathsUtil(u, d, visited, Path_Count): 
    global Graph, V
    visited[u] = True
    
    # If current vertex is same as 
    # destination, then increment count 
    if (u == d): 
        Path_Count[0] += 1
    # If current vertex is not destination 
    else: 
        # Recur for all the vertices 
        # adjacent to current vertex 
        i = 0
        while i < len(Graph[u]): 
            if (not visited[Graph[u][i]]): 
                countPathsUtil(Graph[u][i], d, visited, Path_Count) 
                i += 1
    visited[u] = False

# Returns count of paths from 's' to 'd' 
def Count_Path(s, d): 
    global V
    # Mark all the vertices 
    # as not visited 
    visited = [False] * V 
    
    # Call the recursive helper 
    # function to print all paths 
    Path_Count = [0] 
    countPathsUtil(s, d, visited, Path_Count) 
    
    return Path_Count[0] 
    
# Driver Code 
if __name__ == '__main__': 
    
    # Create a graph given in the 
    # above diagram 
    
    gragh_add(4) 
    addEdge(0, 1) 
    addEdge(0, 2) 
    addEdge(0, 3) 
    addEdge(1, 3)
    addEdge(2, 1) 
    addEdge(2, 3)
    
    s = 0
    d = 3
    print(Count_Path(s, d))