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

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

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

- Mark the currentNode as visited, visited[currentNode] = true
- Add the currentNode to the path
- If currentNode is the destination:
- Add the path to the allPath

- Else:
- Call the getAllPaths function for all the unvisited neighbor nodes

- Mark the currentNode as unvisited, visited[currentNode] = false
- 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
```

Thanks for feedback.