Approach and Explanation
From the given example, what we have to do with this problem is clear. We will be provided with a directed graph and any two vertices as source and destination. We have to find and print all the possible paths from the source to the destination vertex.
Letâ€™s head to our stepbystep approach and learn how to solve the problem at hand.

We have to perform Depth First Search(DFS) on the given graph to find all the possible paths.

To perform the DFS, we start from our given source vertex up to the given destination vertex.

While performing the DFS Algorithm, we maintain an array (say isVisited) and store the incoming or visited vertices.

We maintain the isVisited array to avoid getting stuck. Like in the example, it is possible that our code may forever go back and forth in between vertices 1 and 2, or 2 and 4 because of the direction of traversal.

Such situations are called Cycles. To avoid forming a cycle in our graph, we maintain isVisited.

The array will store 0 on the ith index if the ith vertex has not been visited or 1 if the ith vertex has been visited.

We use a helper function that recursively prints all the possible paths. We call it printAllPathsHelper(). We create all the possible intermediate paths inside this helper function and print them using recursion.

The function takes the following four arguments
 start and end: the two pointers marking the current source vertex and destination vertex.
 isVisited[]: an array that maintains whether a vertex has been visited or not.

tempPathList[]: a temporary array that contains all the path vertices.

The base case of our recursion is when the start and end pointers are equal. In that case, print the array tempPathList[].

Otherwise, mark isVisited[start] to true, and iterate through all the adjacent vertices of the start vertex.

For each iteration, check if the vertex has been visited or not.

If not visited then,
 Add i to tempPathList[]
 Call printAllPathsHelper() at i.

Remove i from tempPathList[].

Once the for loop is complete, mark isVisited[start] to false.
 After all the recursive calls from printAllPathsHelper(), we get our desired outputs.
Java Implementation
import java.util.*;
public class PrintAllPaths{
private final int vertex;
private ArrayList<Integer>[] adjList;
public PrintAllPaths(int vertices) {
vertex = vertices;
initAdjList();
}
@SuppressWarnings(value = "unchecked")
private void initAdjList()
{
adjList = new ArrayList[vertex];
for (int i = 0; i < vertex; i++) {
adjList[i] = new ArrayList<>();
}
}
public void addEdge(int verA, int verB)
{
adjList[verA].add(verB);
}
public void printAllPathsHelper(int start, int end, boolean[] isVisited, List<Integer> tempPathList)
{
if (start == end) {
System.out.println(tempPathList);
return;
}
isVisited[start] = true;
for (Integer i : adjList[start]) {
if (!isVisited[i]) {
tempPathList.add(i);
printAllPathsHelper(i, end, isVisited, tempPathList);
tempPathList.remove(i);//backtracking
}
}
isVisited[start] = false;
}
public void printAllPaths(int source, int dest)
{
boolean[] isVisited = new boolean[vertex];
ArrayList<Integer> pathList = new ArrayList<>();
pathList.add(source);
printAllPathsHelper(source, dest, isVisited, pathList);
}
public static void main(String[] args)
{
PrintAllPaths graph = new PrintAllPaths(5);
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(2, 1);
graph.addEdge(2, 3);
graph.addEdge(2, 4);
graph.addEdge(4, 2);
graph.addEdge(4, 3);
int source = 0;
int dest = 3;
System.out.println("All possible paths from " + source + " to " + dest + " are:");
graph.printAllPaths(source, dest);
}
}
C++ Implementation
/* C++ implementation to print all paths from a source to destination */
#include <iostream>
#include <vector>
using namespace std;
class Graph
{
int V;
vector<int>* adjacencyList;
void printAllPathsUtil(int, int, bool[], int[], int&);
public:
Graph(int V);
void addEdge(int u, int v);
void printAllPaths(int source, int dest);
};
Graph::Graph(int V)
{
this>V = V;
adjacencyList = new vector<int>[V];
}
void Graph::addEdge(int u, int v)
{
adjacencyList[u].push_back(v);
}
void Graph::printAllPaths(int source, int dest)
{
bool* visited = new bool[V];
int* path = new int[V];
int path_index = 0;
for (int i = 0; i < V; i++)
visited[i] = false;
printAllPathsUtil(source, dest, visited, path, path_index);
}
void Graph::printAllPathsUtil(int u, int d, bool visited[],
int path[], int& path_index)
{
visited[u] = true;
path[path_index] = u;
path_index++;
if (u == d)
{
cout<<"[ ";
for (int i = 0; i < path_index; i++)
cout << path[i] << " ";
cout <<"]"<<endl;
}
else
{
vector<int>::iterator i;
for (i = adjacencyList[u].begin(); i != adjacencyList[u].end(); ++i)
if (!visited[*i])
printAllPathsUtil(*i, d, visited, path, path_index);
}
path_index;
visited[u] = false;
}
int main()
{
Graph graph(5);
int source = 0;
int dest = 3;
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(2, 1);
graph.addEdge(2, 3);
graph.addEdge(2, 4);
graph.addEdge(4, 2);
graph.addEdge(4, 3);
cout << "All possible paths from " << source << " to " << dest <<" are:" << endl;
graph.printAllPaths(source, dest);
return 0;
}
Python Implementation
# Python implementation to print all paths from a source to destination
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
def addEdge(self, u, v):
self.graph[u].append(v)
def printAllPathsUtil(self, u, d, visited, path):
visited[u] = True
path.append(u)
if u == d:
print(path)
else:
for i in self.graph[u]:
if visited[i] == False:
self.printAllPathsUtil(i, d, visited, path)
path.pop()
visited[u] = False
def printAllPaths(self, source, destination):
visited = [False]*(self.V)
path = []
self.printAllPathsUtil(source, destination, visited, path)
graph = Graph(5)
graph.addEdge(0, 1)
graph.addEdge(0, 4)
graph.addEdge(1, 2)
graph.addEdge(2, 1)
graph.addEdge(2, 3)
graph.addEdge(2, 4)
graph.addEdge(4, 2)
graph.addEdge(4, 3)
source = 0
destination = 3
print("All possible paths paths from % d to % d :" % (source, destination))
graph.printAllPaths(source, destination)
OUTPUT
All possible paths from 0 to 3 are:
[0, 1, 2, 3]
[0, 1, 2, 4, 3]
[0, 4, 2, 3]
[0, 4, 3]
Complexities
Time Complexity
In the given implementation, we travel v vertices, and in the worst case for each vertex, we can visit v vertices to form a valid path making our solution polynomial. Thus the time complexity is, T(n) = O(V^{V}) where V is the number of vertices.
Space Complexity
In the given implementation, we use polynomial space to find and store our path. Since the total number of paths possible can be O(V^{V}). Thus, Space Complexity = O(V^{V}) where V is the number of vertices.
Frequently Asked Questions
What is a directed graph?
A Graph in which the direction of traversal between the vertices is restricted is called Directed Graph. Generally, the direction of traversal is denoted by an arrow between the two vertices.
What is DFS?
Depth First Search or DFS is a traversal technique in which we travel as far as possible from the source vertex before backtracking. To know more about graph traversal visit, Graph Traversal.
Conclusion
To summarize the article, we learned how to print all paths from a given source to a destination. We first familiarized ourselves with the problem statement with the help of an example. We saw an approach, its Java implementation, and discussed the time and space complexities. To sum it up, we covered a few FAQs.
Want to improve your coding skills? Start practicing problems of various difficulty levels on our Coding Ninjas Studio today.
Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio.
Check out this problem  Root To Leaf Path
Learn about various topics like Programming Fundamentals, Aptitude, DSA, and much more from our CN Library  Free Online Coding Resources.
Also, check out some of the Top Graph Interview Questions to test your understanding of Graphs.
Cheers;)
Happy Coding!