Print all paths from a given source to a destination

Q: What is a directed graph?

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

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.

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,
    - 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);
  }
}

You can also try this code with Online Java Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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.