Find all possible paths in a graph from given source to destination nodes

In this article, we will write a program to find all possible paths from source to destination in a given graph using the Depth First Search Algorithm. The Graph is represented in a 2D Matrix Form in which graph[i][j] == 1 denotes an edge between node i and node j.

Why use DFS?

Since we require all the paths from the source to the destination we can simply traverse the given graph from the source to its depth and find the paths which reach the destination node.

Algorithm

Setup and Initialization in main:

1. Create a list named ‘allPaths’ to store all the paths from source to destination
2. Create a variable named ‘visited’ to keep track of the nodes visited
3. Call the function getAllPaths(source, destination, [empty ArrayList], allPaths, visited, graph)

getAllPaths(currentNode, destination, path, allPaths, visited, graph)

1. Mark the currentNode as visited, visited[currentNode] = true
2. Add the currentNode to the path
3. If currentNode is the destination:
   1. Add the path to the allPath 
4. Else:    
   1. Call the getAllPaths function for all the unvisited neighbor nodes
5. Mark the currentNode as unvisited, visited[currentNode] = false
6. Remove the currentNode from the path

Complexity

• Time Complexity: O(N) 
• Space Complexity: O(N)

Diagram

Code

## Java Code

import java.util.ArrayList;
class Graph {
   public static void getAllPaths(int currentNode, int destination, ArrayList<Integer> path,
           ArrayList<ArrayList<Integer>> allPaths, boolean[] visited, int[][] graph) {
       // Mark the current node as visited and add it to the path
       visited[currentNode] = true;
       path.add(currentNode);


       // Check if we have reached the destination
       if (currentNode == destination) {
           // If destination is reached:
           // Add the copy of the path without reference to the allPaths
           allPaths.add(new ArrayList<>(path));
       } else {
           // If destination is not reached,
           // Traverse to the neighboring unvisited node
           for (int i = 0; i < graph[currentNode].length; i++) {
               if (graph[currentNode][i] == 1 && i != currentNode && !visited[i]) {
                   getAllPaths(i, destination, path, allPaths, visited, graph);
               }
           }
       }


       // Mark the current node again as unvisited and remove it from the path
       visited[currentNode] = false;
       path.remove(path.size() - 1);
   }


   public static void main(String[] args) {
       // We are given a directed unweighted adjacency matrix of a n nodes graph
       int n = 4;
       int source = 2, destination = 3;
       int[][] graph = {
               { 1, 1, 1, 1 },
               { 0, 1, 0, 1 },
               { 1, 1, 1, 0 },
               { 0, 0, 0, 1 }
       };


       // Creating a ArrayList of ArrayList to store all the paths from source to
       // destination
       ArrayList<ArrayList<Integer>> allPaths = new ArrayList<ArrayList<Integer>>();


       // Create a array to store the visited nodes information, the default value of
       // boolean is false
       boolean[] visited = new boolean[n];


       // Run the function to get all the possible path from source to destination
       getAllPaths(source, destination, new ArrayList<Integer>(), allPaths, visited, graph);


       // Print all the paths
       System.out.println("Possible paths are: ");
       for (ArrayList<Integer> path : allPaths) {
           for (Integer node : path) {
               System.out.print(node + " ");
           }
           System.out.println();
       }
   }
}

Output

Possible paths are: 
2 0 1 3 
2 0 3 
2 1 3