Count all possible paths between two vertices - Leetcode Solution

LeetCode: Count all possible paths between two vertices Leetcode Solution

Difficulty: Unknown

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

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