# Print all paths from a given source to a destination

**Introduction**

In this article, we will discuss how to print all paths from a given source to a destination. Such problems are important as they help us understand many concepts related to __Graphs__. We will also learn about __Graph Traversals__ in the due course of this article.

**Problem Statement**

You have been given an unweighted, directed graph and two vertices- a source and a destination. Your task is to print all possible paths from the source vertex to the destination.

**Example**

Sample Input:

Consider the given graph.

Let the source and destination vertices be 0 and 3, respectively.

Expected 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]

**Recommended: Try to solve the problem before heading to the approach and solution code.**

**Approach and Explanation**

From the given example, what we have to do in 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 step-by-step 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, 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 maintain the
- 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[].**

- Add i to

- If not visited then,
- Once the for loop is complete, mark
**isVisited[start]**to false.

- The function takes the following four arguments-
- 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__.

**Key Takeaways**

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 __CodeStudio__ today.

Learn about various topics like Web Technologies, Programing Fundamentals, Aptitude, DSA, and much more from our __CN Library | Free Online Coding Resources__.

Happy Coding!

Comments

## No comments yet

## Be the first to share what you think