**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

- 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)
- Start from the source vertex and make a recursive call to all it adjacent vertices.
- During recursive call, if reach the destination vertex, increment the result (no of paths).
- 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); | |

} | |

} |

**Output**:

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