Count paths between two vertices in undirected graph

Count paths between two vertices in un-directed graph

Count paths for a a given graph G has simple path from source s to destination d. Assume that graph is represented using adjacent matrix.


  • Use DFS
  • When we explored all neighbours of a unvisited vertex then we set visited of that vertex to false so, that we ca n use for next iteration
  1.  Set count = 0
  2. Create boolean visited matrix for each vertex of graph G
  3. Call Count_Path function
  4. In count_path function
    1. Set visited of source_vertex to true
    2. If source_vertex == destination_vertex then
      1. Increment vertext counter
      2. Set visited of destination_vertex to false
    3. Explore all adjacent_vertices of sources_vertex
    4. If adjacent_vertex is not visited then
      1. Call count_path recursively with adjacent_vertex as sources vertex
      2. After exploring all neighbours of adjacent_vertex set visited of this vertex to false

Latest Source Code:


 -   T   T   T   -  
 T   -   -   T   -  
 T   -   -   T   -  
 T   T   T   -   T  
 -   -   -   T   -  
Path Count between 0 to 5 are: 3
Author: Hrishikesh Mishra