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:


Output:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • lipsa patel

    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) {

    pathCount++;
    }
    }

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

%d bloggers like this: