**Objective**: Given a graph, source vertex and destination vertex. Write an algorithm to print all possible paths between source and destination.

This problem also is known as “Print all paths between two nodes”

**Example:**:

**Approach**: Use Depth First Search

- Start from the source vertex and visit the next vertex (use adjacency list).
- Now if you look carefully, the new problem is to find paths from the current vertex to destination. For instance as per the example above, start from vertex 0 and visit vertex 1. Now all the paths from vertex 1 to vertex 5 will be included in our final result if we add vertex 0. So make a recursive call with source as vertex 1 and destination as vertex 5.
- Keep track of visited nodes to avoid cycles.
- Add current vertex to result (taking string here) to keep track of path from source.
- Once reach to the destination vertex, print the path.
- Now visit the next node in adjacency list in step 1 and repeat all the steps (loop)
- See the code for more understanding.

**Code**:

import java.util.LinkedList; | |

public class GraphPrintAllPaths { | |

public void print(Graph graph, int start, int end, String path, boolean[] visited){ | |

String newPath = path + "->" + start; | |

visited[start] = true; | |

LinkedList<Node> list = graph.adjacencyList[start]; | |

for (int i = 0; i <list.size() ; i++) { | |

Node node = list.get(i); | |

if(node.destination!=end && visited[node.destination]==false){ | |

// visited[node.destination] = true; | |

print(graph,node.destination,end,newPath,visited); | |

}else if(node.destination==end){ | |

System.out.println(newPath + "->" + node.destination); | |

} | |

} | |

//remove from path | |

visited[start] = false; | |

} | |

public void printAllPaths(Graph graph, int start, int end){ | |

boolean[] visited = new boolean[graph.vertices]; | |

visited[start] = true; | |

print(graph, start, end, "", visited); | |

} | |

public static void main(String[] args) { | |

int vertices = 6; | |

Graph graph = new Graph(vertices); | |

graph.addEdge(0, 1); | |

graph.addEdge(0, 2); | |

graph.addEdge(1, 2); | |

graph.addEdge(1, 3); | |

graph.addEdge(3, 4); | |

graph.addEdge(2, 3); | |

graph.addEdge(4, 0); | |

graph.addEdge(4, 1); | |

graph.addEdge(4, 5); | |

GraphPrintAllPaths p = new GraphPrintAllPaths(); | |

p.printAllPaths(graph,0,5); | |

} | |

} | |

class Graph{ | |

int vertices; | |

LinkedList<Node> [] adjacencyList; | |

public Graph(int vertices){ | |

this.vertices = vertices; | |

adjacencyList = new LinkedList[vertices]; | |

for (int i = 0; i <vertices; i++) { | |

adjacencyList[i] = new LinkedList<Node>(); | |

} | |

} | |

public void addEdge(int source, int destination){ | |

Node node = new Node(source, destination); | |

//add edge | |

adjacencyList[source].addLast(node); | |

} | |

} | |

class Node{ | |

int source; | |

int destination; | |

public Node(int source, int destination) { | |

this.source = source; | |

this.destination = destination; | |

} | |

} |

**Output**:

->0->1->2->3->4->5 ->0->1->3->4->5 ->0->2->3->4->5