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<Integer>[] adjList;
Graph(int vertices){
this.vertices = vertices;
adjList = new LinkedList[vertices];
for (int i = 0; i <vertices ; i++) {
adjList[i] = new LinkedList<>();
}
}
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