# Graph – Count all paths between source and destination

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

Condition: Graph does not contain any cycle.

This problem also known as “paths between two nodes” Example:

Approach: Use Depth First Search

1. Use DFS but we cannot use visited [] to keep track of visited vertices since we need to explore all the paths. visited [] is used avoid going into cycles during iteration. (That is why we have a condition in this problem that graph does not contain cycle)
2. Start from the source vertex and make a recursive call to all it adjacent vertices.
3. During recursive call, if reach the destination vertex, increment the result (no of paths).
4. See the code for more understanding.

Code:

 import java.util.LinkedList; public class CountPaths { static int paths =0; static class Graph{ int vertices; LinkedList[] adjList; Graph(int vertices){ this.vertices = vertices; adjList = new LinkedList[vertices]; for (int i = 0; i (); } } public void addEgde(int source, int destination){ adjList[source].addFirst(destination); } public void countPaths(int source, int destination){ count(source, destination); System.out.println("No of paths between source: " + source + " and destination: " + destination + " are:" + paths); } public void count(int start, int destination){ if(start==destination) { paths++; }else { for (int i = 0; i < adjList[start].size(); i++) { int ajdacentVertex = adjList[start].get(i); count(ajdacentVertex, destination); } } } } public static void main(String[] args) { int vertices = 6; Graph graph = new Graph(vertices); graph.addEgde(0, 1); graph.addEgde(0, 2); graph.addEgde(1, 2); graph.addEgde(1, 3); graph.addEgde(3, 4); graph.addEgde(2, 3); graph.addEgde(4, 5); int source =0; int destination=5; graph.countPaths(source,destination); } }

view raw
CountPaths.java
hosted with ❤ by GitHub

Output:

`No of paths between source: 0 and destination: 5 are: 3`