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”


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.



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

1 thought on “Graph – Count all paths between source and destination”

  1. You can even do with cycles. Set visited[start] = false when returning

    private static void countAllPaths(int start, int end, boolean[] visited) {

    visited[start] = true;

    LinkedList adjacentList = graphList[start];

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

    int destination = adjacentList.get(i);

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

    countAllPaths(destination, end, visited);

    } else if (destination == end) {


    //Remove to start again
    visited[start] = false;


Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.