# Count all possible paths between two vertices

Count the total number of ways or paths that exist between two vertices in a directed graph. These paths doesn’t contain a cycle, the simple enough reason is that a cylce contain infinite number of paths and hence they create problem.

Examples:

```Input : Count paths between A and E Output : Total paths between A and E are 4
Explanation: The 4 paths between A and E are:
A -> E
A -> B -> E
A -> C -> E
A -> B -> D -> C -> E
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The problem can be solved using backtracking, that is we take a path and start walking it, if it leads us to the destination vertex then we count the path and backtrack to take another path. If the path doesn’t leads us to the destination vertex, we discard the path.

Backtracking for above graph can be shown like this:
The red color vertex is the source vertex and the light-blue color vertex is destination, rest are either intermediate or discarded paths. This gives us four paths between source(A) and destination(E) vertex.

Problem Associated with this: Now if we add just one more edge between C and B, it would make a cycle (B -> D -> C -> B). And hence we could loop the cycles any number of times to get a new path, and there would be infinitely many paths because of the cycle. ## C++

 `// C++ program to count all paths from a  ` `// source to a destination. ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// A directed graph using adjacency list ` `// representation ` `class` `Graph ` `{ ` `     `  `    ``// No. of vertices in graph ` `    ``int` `V;  ` `    ``list<``int``> *adj; ` ` `  `    ``// A recursive function ` `    ``// used by countPaths() ` `    ``void` `countPathsUtil(``int``, ``int``, ``bool` `[], ` `                                  ``int` `&); ` ` `  `public``: ` ` `  `    ``// Constructor ` `    ``Graph(``int` `V);  ` `    ``void` `addEdge(``int` `u, ``int` `v); ` `    ``int` `countPaths(``int` `s, ``int` `d); ` `}; ` ` `  `Graph::Graph(``int` `V) ` `{ ` `    ``this``->V = V; ` `    ``adj = ``new` `list<``int``>[V]; ` `} ` ` `  `void` `Graph::addEdge(``int` `u, ``int` `v) ` `{ ` `     `  `    ``// Add v to u’s list. ` `    ``adj[u].push_back(v);  ` `} ` ` `  `// Returns count of paths from 's' to 'd' ` `int` `Graph::countPaths(``int` `s, ``int` `d) ` `{ ` `     `  `    ``// Mark all the vertices ` `    ``// as not visited ` `    ``bool` `*visited = ``new` `bool``[V]; ` `    ``memset``(visited, ``false``, ``sizeof``(visited)); ` ` `  `    ``// Call the recursive helper ` `    ``// function to print all paths ` `    ``int` `pathCount = 0; ` `    ``countPathsUtil(s, d, visited, pathCount); ` `    ``return` `pathCount; ` `} ` ` `  `// 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[] ` `void` `Graph::countPathsUtil(``int` `u, ``int` `d, ``bool` `visited[], ` `                                        ``int` `&pathCount) ` `{ ` `    ``visited[u] = ``true``; ` ` `  `    ``// If current vertex is same as destination,  ` `    ``// then increment count ` `    ``if` `(u == d) ` `        ``pathCount++; ` ` `  `    ``// If current vertex is not destination ` `    ``else` `    ``{ ` `        ``// Recur for all the vertices adjacent to ` `        ``// current vertex ` `        ``list<``int``>::iterator i; ` `        ``for` `(i = adj[u].begin(); i != adj[u].end(); ++i) ` `            ``if` `(!visited[*i]) ` `                ``countPathsUtil(*i, d, visited,  ` `                                      ``pathCount); ` `    ``} ` ` `  `    ``visited[u] = ``false``; ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `     `  `    ``// Create a graph given in the above diagram ` `    ``Graph g(4); ` `    ``g.addEdge(0, 1); ` `    ``g.addEdge(0, 2); ` `    ``g.addEdge(0, 3); ` `    ``g.addEdge(2, 0); ` `    ``g.addEdge(2, 1); ` `    ``g.addEdge(1, 3); ` ` `  `    ``int` `s = 2, d = 3; ` `    ``cout << g.countPaths(s, d); ` ` `  `    ``return` `0; ` `}  `

## Java

 `// Java program to count all paths from a source ` `// to a destination. ` `import` `java.util.Arrays; ` `import` `java.util.Iterator; ` `import` `java.util.LinkedList; ` ` `  `// This class represents a directed graph using  ` `// adjacency list representation ` ` `  `class` `Graph { ` `     `  `    ``// No. of vertices ` `    ``private` `int` `V;  ` ` `  `    ``// Array of lists for ` `    ``// Adjacency List  ` `    ``// Representation ` `    ``private` `LinkedList adj[]; ` ` `  `    ``@SuppressWarnings``(``"unchecked"``) ` `    ``Graph(``int` `v)  ` `    ``{ ` `        ``V = v; ` `        ``adj = ``new` `LinkedList[v]; ` `        ``for` `(``int` `i = ``0``; i < v; ++i) ` `            ``adj[i] = ``new` `LinkedList<>(); ` `    ``} ` ` `  `    ``// Method to add an edge into the graph ` `    ``void` `addEdge(``int` `v, ``int` `w) ` `    ``{ ` `         `  `        ``// Add w to v's list. ` `        ``adj[v].add(w);  ` `    ``} ` ` `  `     `  `    ``// A recursive method to count ` `    ``// all paths from 'u' to 'd'. ` `    ``int` `countPathsUtil(``int` `u, ``int` `d, ` `                    ``boolean` `visited[],  ` `                    ``int` `pathCount) ` `    ``{ ` `         `  `        ``// Mark the current node as ` `        ``// visited and print it ` `        ``visited[u] = ``true``; ` ` `  `        ``// If current vertex is same as  ` `        ``// destination, then increment count ` `        ``if` `(u == d)  ` `        ``{ ` `            ``pathCount++; ` `        ``} ` `             `  `        ``// Recur for all the vertices ` `        ``// adjacent to this vertex ` `        ``else` `        ``{ ` `            ``Iterator i = adj[u].listIterator(); ` `            ``while` `(i.hasNext())  ` `            ``{ ` `                ``int` `n = i.next(); ` `                ``if` `(!visited[n])  ` `                ``{ ` `                    ``pathCount = countPathsUtil(n, d, ` `                                            ``visited, ` `                                            ``pathCount); ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``visited[u] = ``false``; ` `        ``return` `pathCount; ` `    ``} ` ` `  `    ``// Returns count of ` `    ``// paths from 's' to 'd' ` `    ``int` `countPaths(``int` `s, ``int` `d) ` `    ``{ ` `         `  `        ``// Mark all the vertices ` `        ``// as not visited ` `        ``boolean` `visited[] = ``new` `boolean``[V]; ` `        ``Arrays.fill(visited, ``false``); ` ` `  `        ``// Call the recursive method ` `        ``// to count all paths ` `        ``int` `pathCount = ``0``; ` `        ``pathCount = countPathsUtil(s, d, ` `                                ``visited,  ` `                                ``pathCount); ` `        ``return` `pathCount; ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String args[])  ` `    ``{ ` `        ``Graph g = ``new` `Graph(``4``); ` `        ``g.addEdge(``0``, ``1``); ` `        ``g.addEdge(``0``, ``2``); ` `        ``g.addEdge(``0``, ``3``); ` `        ``g.addEdge(``2``, ``0``); ` `        ``g.addEdge(``2``, ``1``); ` `        ``g.addEdge(``1``, ``3``); ` ` `  `        ``int` `s = ``2``, d = ``3``; ` `        ``System.out.println(g.countPaths(s, d)); ` `    ``} ` `} ` ` `  `// This code is contributed by shubhamjd. `

## Python3

 `# Python 3 program to count all paths  ` `# from a source to a destination.  ` ` `  `# A directed graph using adjacency  ` `# list representation  ` `class` `Graph: ` ` `  `    ``def` `__init__(``self``, V): ` `        ``self``.V ``=` `V  ` `        ``self``.adj ``=` `[[] ``for` `i ``in` `range``(V)] ` `     `  `    ``def` `addEdge(``self``, u, v): ` `         `  `        ``# Add v to u’s list.  ` `        ``self``.adj[u].append(v) ` `     `  `    ``# Returns count of paths from 's' to 'd'  ` `    ``def` `countPaths(``self``, s, d): ` `         `  `        ``# Mark all the vertices  ` `        ``# as not visited  ` `        ``visited ``=` `[``False``] ``*` `self``.V ` `     `  `        ``# Call the recursive helper  ` `        ``# function to prall paths  ` `        ``pathCount ``=` `[``0``]  ` `        ``self``.countPathsUtil(s, d, visited, pathCount)  ` `        ``return` `pathCount[``0``] ` `     `  `    ``# A recursive function to prall 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(``self``, u, d,  ` `                       ``visited, pathCount): ` `        ``visited[u] ``=` `True` `     `  `        ``# If current vertex is same as  ` `        ``# destination, then increment count  ` `        ``if` `(u ``=``=` `d): ` `            ``pathCount[``0``] ``+``=` `1` `     `  `        ``# If current vertex is not destination  ` `        ``else``: ` `             `  `            ``# Recur for all the vertices  ` `            ``# adjacent to current vertex ` `            ``i ``=` `0` `            ``while` `i < ``len``(``self``.adj[u]): ` `                ``if` `(``not` `visited[``self``.adj[u][i]]):  ` `                    ``self``.countPathsUtil(``self``.adj[u][i], d,  ` `                                        ``visited, pathCount) ` `                ``i ``+``=` `1` `     `  `        ``visited[u] ``=` `False` ` `  `# Driver Code  ` `if` `__name__ ``=``=` `'__main__'``: ` ` `  `    ``# Create a graph given in the  ` `    ``# above diagram  ` `    ``g ``=` `Graph(``4``)  ` `    ``g.addEdge(``0``, ``1``)  ` `    ``g.addEdge(``0``, ``2``)  ` `    ``g.addEdge(``0``, ``3``)  ` `    ``g.addEdge(``2``, ``0``)  ` `    ``g.addEdge(``2``, ``1``)  ` `    ``g.addEdge(``1``, ``3``)  ` ` `  `    ``s ``=` `2` `    ``d ``=` `3` `    ``print``(g.countPaths(s, d)) ` ` `  `# This code is contributed by PranchalK `

Output:

```3
```

This article is attributed to GeeksforGeeks.org

## tags:

Backtracking Graph DFS DFS Graph Backtracking

code

load comments