 # 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.

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 += 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 += 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 = 
countPathsUtil(s, d, visited, Path_Count)

return Path_Count

# 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))```
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.