This post is completed by 1 user

  • 1
Add to List

277. 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