# Print all the paths between two nodes in a Graph

In this tutorial we will learn how to find all the simple paths(paths without a cycle) between two nodes in a graph. We are given a graph, a source node, and a destination node and we have to find all the paths originating from source node to ending at destination node.

**Depth First Search(DFS)** is generally used when finding a simple path between two nodes. Our problem is similar to that as we have to find out not just any single path but all the paths. So we will tweak the DFS algorithm a little to print all possible paths. The basic idea is that, after the destination node is found by DFS, print the path and mark it as unvisited so that DFS could continue finding all the remaining paths.

For example, let’s take a **complete graph** for five nodes. Graph is given as 2-D matrix. Here’s the graph

0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 5

The last two entries of 1 and 5 are source and destination nodes respectively. This graph will look like this

A sample solution to the problem :

import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; import java.io.InputStreamReader; class AllPathBetweenTwoNodes{ static int dim = 5; // dim is number of nodes in graph //color is used to mark if the node is visited or not static boolean[] color = new boolean[dim + 1]; //graph is given in 2-D matrix form static int[][] graph = new int[10][10]; // this list will store nodes on the path from source to destination static ArrayList<Integer> list = new ArrayList<Integer>(); // this is the size of "list" declared above // size is used to remember index of the node in the list to be removed // when the node is marked unvisited static int size; public static void main (String ... args) throws IOException{ BufferedReader br = new BufferedReader (/*new FileReader("input.txt")*/new InputStreamReader ((System.in))); for (int I = 1; I <= dim; I++) { String[] input = br.readLine().split(" "); int len = input.length; for (int J = 1; J <= len; J++) { graph[I][J] = Integer.parseInt(input[J - 1]); } } Arrays.fill(color, false); // initially all are unvisited int src = Integer.parseInt(br.readLine()); //Source node int dst = Integer.parseInt(br.readLine()); //Destination node dfs(src, dst); // backtracking } static void dfs(int src, int dst) { //node added to path list.add(src); size++; //node marked as visited color[src] = true; //when the destination node is found if (src == dst) { // Print the path for (Integer node : list) { System.out.print(node + " "); } System.out.println(); return; } for (int I = 1; I <= dim; I++) { // if there's an edge between src and node if (graph[src][I] == 1) { //and that node is not visited yet if (color[I] == false) { //start dfs from that node dfs(I, dst); //This line is critical to understand //it marks the node unvisited which we have just visited //so that the dfs could find another path to destination color[I] = false; //size of list reduced by 1 //as the node is marked unvisited //hence removed from the list size--; //remove that node at index "size" from list list.remove(size); } } } } }

This code print all the paths between node 1(source) and 5(destination). All the paths will be :

1 2 3 4 5 1 2 3 5 1 2 4 3 5 1 2 4 5 1 2 5 1 3 2 4 5 1 3 2 5 1 3 4 2 5 1 3 4 5 1 3 5 1 4 2 3 5 1 4 2 5 1 4 3 2 5 1 4 3 5 1 4 5 1 5

Comments in the code make it self-explanatory, still for any doubts please drop a comment. Thanks for reading. Have a nice day!!!