1.
Introduction
2.
Problem Statement
3.
Approach and Explanation
3.1.
Java Implementation
3.2.
C++ Implementation
3.3.
Python Implementation
3.4.
Complexities
4.
4.1.
What is a directed graph?
4.2.
What is DFS?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Print all Paths from a Given Source to a Destination

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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

Also, see Data Structures

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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 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 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,
• 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;

public PrintAllPaths(int vertices) {
vertex = vertices;
}

@SuppressWarnings(value = "unchecked")
{
for (int i = 0; i < vertex; i++) {
}
}
public void addEdge(int verA, int 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]) {
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<>();
printAllPathsHelper(source, dest, isVisited, pathList);
}

public static void main(String[] args)
{
PrintAllPaths graph = new PrintAllPaths(5);

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;
void printAllPathsUtil(int, int, bool[], int[], int&);

public:
Graph(int V);
void printAllPaths(int source, int dest);
};

Graph::Graph(int V)
{
this->V = 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;
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;

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)

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)

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(VV) 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(VV). Thus, Space Complexity = O(VV) where V is the number of vertices.

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

Live masterclass