Skip to main content

Count all possible paths between two vertices

Counting all possible paths between two vertices in a graph involves finding the total number of distinct paths that can be taken from a starting vertex to a destination vertex, while traversing the edges of the graph.

The number of paths between two vertices can be computed using a graph traversal algorithm, such as depth-first search (DFS) or breadth-first search (BFS), which can explore all possible paths between two vertices.

The basic idea is to start from the source vertex, and explore all its adjacent vertices, recursively repeating the process for each adjacent vertex until the destination vertex is reached. During the traversal, we keep track of the number of paths that we have explored from the source vertex to the destination vertex.

Counting all paths between two nodes in graph

Here is the algorithm to count all possible paths between two vertices in a graph:

  1. Initialize a variable count to 0.
  2. Start a DFS or BFS traversal from the source vertex.
  3. For each adjacent vertex of the current vertex that has not been visited yet, recursively call the traversal function.
  4. If the current vertex is the destination vertex, increment the count by 1.
  5. When the traversal is complete, return the count.

Note that this algorithm assumes that the graph is a directed graph, meaning that the edges have a specific direction. If the graph is undirected, meaning that edges can be traversed in both directions, we would need to modify the algorithm to avoid revisiting nodes that we have already explored.

Program List

//C Program to 
//Count all possible paths between two vertices
#include<stdio.h>
#include<stdlib.h>

struct AjlistNode{
  int vId;//Vertices id
  struct AjlistNode*next;
};

struct Graph{
  int data; //node key value
  struct AjlistNode*next;
};



int size; //number of nodes

//set node key value
void setData(struct Graph*node)
{
  if(node!=NULL && size>0)
  {
    int index=0;
    for(index;index<size;index++)
    {
      //set vertic node data
      node[index].data=index;//set node key
      //Initial no AjlistNode
      //set NULL Value
      node[index].next=NULL;
    }
  }else{
    printf("Vertic Node is Empty");
  }
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
  if(V<size && E <size)
  {
      //first create Adjacency node
    struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
      sizeof(struct AjlistNode)
      );
    if(newEdge!=NULL)
    {

      newEdge->next=NULL;
      newEdge->vId=E;

      struct AjlistNode *temp=node[V].next;

      if(temp==NULL)
      {
        node[V].next=newEdge;
      }else
      {
                //Add node at last
        while(temp->next!=NULL)
        {
          temp=temp->next;
        }      
        temp->next=newEdge;          
      }
    }else
    {
      printf("\n Memory overflow");
    }
  }else
  {
      //not valid Vertices
    printf("Invalid Node Vertices %d  %d", V,E);
  }
}
//Display Adjacency list of vertex
void printGraph(struct Graph*node)
{
  if(node!=NULL)
  {
    struct AjlistNode *temp=NULL;
    for(int index=0;index<size;index++)
    {
      printf("\n Adjacency list of vertex %d  :",index);
      temp=node[index].next;
      while(temp!=NULL)
      {
        //temp->vId is graph node vertices
        //in this case temp->vId is same as 
        //node[temp->vId].data

        printf("  %d",node[temp->vId].data);
        temp=temp->next;
      }
    }
  }else
  {
    printf("Empty Graph");
  }
}


//This function are capable to count all path between two nodes
void count_path(int start,
  int end,
  int *visit,
  struct Graph*node,
  int*result)
{

  if(start >size 
    || end >size 
    || start<0 
    || end<0 
    || node==NULL)
  {
    //invalid node location
    return ;
  }

  if(visit[start]==1)
  {
    //node is already visited
    return;
  }
  if(start==end)
  {
    //when source and destination are get
    *result=(*result)+1;
  }
  //active the visiting node status
  visit[start]=1;

  struct AjlistNode *temp=node[start].next;

  while(temp!=NULL)
  {
    //check node by edges
    count_path(temp->vId,end,visit,node,result); 

    temp=temp->next;
  }
  //inactive current visiting node status
  visit[start]=0;
}


int main()
{

  size=6; //set number of nodes
  struct Graph*node=NULL;

  int *visit=(int*)calloc(size,sizeof(int));

  //Creating memory of graph nodes
  node=(struct Graph*)malloc(sizeof(struct Graph)*size);
  
  if(node==NULL)
  {
    printf("\n Memory overflow");

  }else
  {
    //First set node keys
    setData(node); 

    //Connected two node with Edges
    addEdge(node,0, 1); 
    addEdge(node,0, 3); 
    addEdge(node,1, 2); 
    addEdge(node,1, 4); 
    addEdge(node,2, 3); 
    addEdge(node,2, 4); 
    addEdge(node,2, 5); 
    addEdge(node,3, 1); 
    addEdge(node,3, 5); 
    addEdge(node,5, 4); 



    printGraph(node);

    //value 0 is source node
    int source = 0;

    //value 4 is destination node
    int destination = 4;

    //for resultant paths
    int result=0;

    count_path(source,destination,visit,node,&result);

    printf("\n Possible Path : %d\n",result );
  }  
  return 0;
}

Output

 Adjacency list of vertex 0  :  1  3
 Adjacency list of vertex 1  :  2  4
 Adjacency list of vertex 2  :  3  4  5
 Adjacency list of vertex 3  :  1  5
 Adjacency list of vertex 4  :
 Adjacency list of vertex 5  :  4
 Possible Path : 8

//C++ program
//Count all possible paths between two vertices
#include <iostream>
using namespace std;

struct AjlistNode
{
    int vId;//Vertices id
    struct AjlistNode*next;
  };

  struct Vertices
  {
    int data; //node key value
    struct AjlistNode*next;
  };


  class Graph
  {
    Vertices *node;
  int size;//number of 
public:
  Graph(int);
  void setData();
  void addEdge(int,int);
  void printGraph();
  void connect(int  ,int );
  void count_path(int,int ,int* ,int*);
  void total_path(int,int);
};
Graph::Graph(int size)
{
  this->size = size;
    //set number of nodes
  node = new Vertices[size];
}
//set node key value
void Graph:: setData()
{
  if(node!=NULL)
  {
    int index=0;

    for(index;index<size;index++)
    {
      //set vertic node data
      node[index].data=index;//set node key
      //Initial no AjlistNode
      //set NULL Value
      node[index].next=NULL;
    }
  }
  else
  {
    cout<<"Vertic Node is Empty"<<endl;
  }
}
//Add Edge from Two given Nodes
void Graph ::connect(int start ,int end)
{
    //add edge form start to end
    //start and end is Node location
    //first create Adjacency node
  AjlistNode *newEdge=new AjlistNode;

  if(newEdge!=NULL)
  {

    newEdge->next = NULL;
    newEdge->vId = end;

    AjlistNode *temp=node[start].next;

    if(temp==NULL)
    {
      node[start].next=newEdge;
    }else
    {
            //Add node at last
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }      
      temp->next=newEdge;          
    }
  }

}


void Graph ::  addEdge(int V ,int E)
{
  //add edge form V to E
  //V and E is Node location
  if(V<size && E <size)
  {
    connect(V,E);

  }else
  {
        //not valid Vertices
    cout<<"Invalid Node Vertices "<< V<<" "<<E;
  }
}

//Display Adjacency list of vertex
void Graph:: printGraph()
{
  if(node!=NULL)
  {
    AjlistNode *temp=NULL;
    for(int index=0; index < size; index++)
    {
      cout<<"\n Adjacency list of vertex "<<index<<" :";
      temp=node[index].next;
      while(temp!=NULL)
      {
        //temp->vId is graph node vertices
        //in this case temp->vId is same as 
        //node[temp->vId].data

        cout<<" "<<node[temp->vId].data;
        temp=temp->next;
      }
    }
  }else
  {
    cout<<"Empty Graph"<<endl;
  }
}


//This function are capable to count all path between two nodes
void Graph:: count_path(int start,
 int end,
 int *visit,
 int*result)
{
  if(start >size 
   || end >size 
   || start<0 
   || end<0 
   || node==NULL)
  {
    //invalid node location
    return ;
  }
  if(visit[start]==1)
  {
    //node is already visited
    return;
  }
  if(start==end)
  {
    //when source and destination are get
    *result=(*result)+1;
  }
  //active the visiting node status
  visit[start]=1;
  AjlistNode *temp=node[start].next;
  while(temp!=NULL)
  {
    //check node by edges
    count_path(temp->vId,end,visit,result); 
    temp=temp->next;
  }
  //inactive current visiting node status
  visit[start]=0;
}

void Graph :: total_path(int source,int destination)
{
   //for resultant paths
  int result=0;
  int visit[size];
  for(int i=0;i<size;i++)
  {
    visit[i]=0;
  }
  count_path(source,destination,visit,&result);
  cout<<"\n Possible Path : "<<result<<"\n";
}

int main()
{
  //Create Object
  Graph g=Graph(6); //6 nodes
  //First set node keys
  g.setData();

  //Connected two node with Edges
  g.addEdge(0, 1); 
  g.addEdge(0, 3); 
  g.addEdge(1, 2); 
  g.addEdge(1, 4); 
  g.addEdge(2, 3); 
  g.addEdge(2, 4); 
  g.addEdge(2, 5); 
  g.addEdge(3, 1); 
  g.addEdge(3, 5); 
  g.addEdge(5, 4); 

  g.printGraph();

  //value 0 is source node
  int source = 0;
  //value 4 is destination node
  int destination = 4;

  g.total_path(source,destination);
 
  return 0;
}

Output

 Adjacency list of vertex 0 : 1 3
 Adjacency list of vertex 1 : 2 4
 Adjacency list of vertex 2 : 3 4 5
 Adjacency list of vertex 3 : 1 5
 Adjacency list of vertex 4 :
 Adjacency list of vertex 5 : 4
 Possible Path : 8

//Java program
//Count all possible paths between two vertices
public class MyGraph
{

    static class AjlistNode
    {
        int id;//Vertices node key
        AjlistNode next;
    }
    static class Vertices
    {
        int data;
        AjlistNode next;
    }

    //number of Vertices
    public int size,result;
    Vertices node[];

    MyGraph(int size)
    {
        //set value
        this.size = size;
        result = 1;
        node = new Vertices[size];
        
    }

    //set initial node value
    public void setData()
    {
        if(node == null)
        {
            System.out.println("\nEmpty Graph");
        }else
        {
            for(int index = 0; index < size; index++)
            {
                // avoid java.lang.nullPointerException
                node[index]=new Vertices(); 
                node[index].data=index;//set your data
                node[index].next=null;
            }
        }
    }
    //connect two nodes
    public void connect(int start,int end)
    {
        AjlistNode newEdge=new AjlistNode();
        newEdge.id=end;//end node
        newEdge.next=null;
        if(node[start].next==null)
        {
            node[start].next=newEdge;
        }else
        {
            AjlistNode temp=node[start].next;

            while(temp.next!=null)
            {
                temp=temp.next;
            }
            temp.next=newEdge;
        }
    }
    //Add edge at the end
    public void addEdge(int start,int end)
    {
        if(start < size && end < size && node != null)
        {
           connect(start,end);
           
        }else{
            System.out.println("\nEmpty Graph");
        }
    }

    public void printGraph()
    {

        if(size>0 && node!=null)
        {
            for(int index=0;index < size;index++)
            {
                System.out.print("\nAdjacency list of vertex "+index+" :");
                
                AjlistNode temp=node[index].next;

                while(temp!=null)
                {
                    System.out.print("  "+node[temp.id].data);

                    temp=temp.next;
                }
            }
        }
    }
    //This function are capable to count all path between two nodes
    public void  count_path(int start,int end,boolean []visit)
    {
      if(start >size 
       || end >size 
       || start<0 
       || end<0 
       || node==null)
      {
        //invalid node location
        return ;
      }
      if(visit[start]==true)
      {
        //node is already visited
        return;
      }
      if(start==end)
      {
        //when source and destination are get
         result=result+1;
      }
      //active the visiting node status
      visit[start]=true;
      AjlistNode  temp=node[start].next;
      while(temp!=null)
      {
        //check node by edges
        count_path(temp.id,end,visit); 
        temp=temp.next;
      }
      //inactive current visiting node status
      visit[start]=false;
    }

    public void  total_path(int source,int destination)
    {
      //for resultant paths
      result=0;
      boolean []visit=new boolean[size];
      for(int i=0;i<size;i++)
      {
        visit[i]=false;
      }
      count_path(source,destination,visit);
      System.out.println("\n Possible Path : "+result);
    }
    
    public static void main(String[] args) 
    {
        int totalNode=6;

        MyGraph g=new MyGraph(totalNode);
        
        g.setData();

        //Connected two node with Edges
        g.addEdge(0, 1); 
        g.addEdge(0, 3); 
        g.addEdge(1, 2); 
        g.addEdge(1, 4); 
        g.addEdge(2, 3); 
        g.addEdge(2, 4); 
        g.addEdge(2, 5); 
        g.addEdge(3, 1); 
        g.addEdge(3, 5); 
        g.addEdge(5, 4); 

        g.printGraph();

        //value 0 is source node
        int source = 0;
        //value 4 is destination node
        int destination = 4;

        g.total_path(source,destination);

    }
}

Output

Adjacency list of vertex 0 :  1  3
Adjacency list of vertex 1 :  2  4
Adjacency list of vertex 2 :  3  4  5
Adjacency list of vertex 3 :  1  5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 :  4
 Possible Path : 8

#Python program
#Count all possible paths between two vertices
#Using DFS
class AjLinkeNode:
  def __init__(self,data):
    self.id=data
    self.next=None

class Vertices:
  def __init__(self,data):
    self.data=data
    self.next=None

class Graph:
  """Constructor for Graph"""
  def __init__(self, size):
    self.size=size
    self.node=[]
    self.result=0
    

  def setData(self):
    if(self.size>0 and self.node!=None):

      index=0
      while(index<self.size):

        self.node.append(Vertices(index))

        index+=1


  #connect two node with  edge
  def connect(self,start,end):

    new_edge=AjLinkeNode(end)

    if(self.node[start].next==None):

      self.node[start].next=new_edge
    else:

      temp=self.node[start].next

      while(temp.next!=None):

        temp=temp.next

      temp.next=new_edge  

  #add edge
  def addEdge(self,start,end):
     
    #start,end is two nodes
    if(self.size > start and self.size > start):
      
      self.connect(start,end)

    else:
      print("Invalid nodes")


  def printGraph(self):

    if(self.size>0 and self.node!=None):

      index=0

      while(index < self.size):

        print("\nAdjacency list of vertex {0} : ".format(index),end=" ")
        
        temp=self.node[index].next
        
        while temp!=None:

          print(" {0}".format(temp.id),end=" ")

          temp=temp.next

        index+=1

  
  #This function are capable to count all path between two nodes
  def count_path(self,start,end,visit) :

    if(start >self.size  or  end >self.size or start<0 or end<0 or self.node==None) :

      #invalid node location
      return 
    if(visit[start]==True) :

      #node is already visited
      return
    if(start==end) :

      #when source and destination are get
      self.result+=1

    #active the visiting node status
    visit[start]=True
    temp=self.node[start].next
    while(temp!=None) :

      #check node by edges
      self.count_path(temp.id,end,visit) 
      temp=temp.next

    #inactive current visiting node status
    visit[start]=False

  def  total_path(self,source,destination) :

    #for resultant paths
    self.result=0
    visit=[False]*self.size

    self.count_path(source,destination,visit)
    print("\n Possible Path : ",self.result)
    


    
def main():
  g=Graph(6)
  g.setData() 
  #Connected two node with Edges
  g.addEdge(0, 1) 
  g.addEdge(0, 3) 
  g.addEdge(1, 2) 
  g.addEdge(1, 4) 
  g.addEdge(2, 3) 
  g.addEdge(2, 4) 
  g.addEdge(2, 5) 
  g.addEdge(3, 1) 
  g.addEdge(3, 5) 
  g.addEdge(5, 4) 
  g.printGraph()
  #value 0 is source node
  source = 0
  #value 4 is destination node
  destination = 4
  g.total_path(source,destination)

if __name__=="__main__":
    main()

Output

Adjacency list of vertex 0 :   1  3 
Adjacency list of vertex 1 :   2  4 
Adjacency list of vertex 2 :   3  4  5 
Adjacency list of vertex 3 :   1  5 
Adjacency list of vertex 4 :  
Adjacency list of vertex 5 :   4 
 Possible Path :  8

//C# program
//Count all possible paths between two vertices
//Using DFS
using System;
public class AjlistNode
{
  public int id;//Vertices node key
  public AjlistNode next;
}
public class Vertices
{
  public int data;
  public AjlistNode next;
}

public class MyGraph
{

  //number of Vertices
  public int size,result;
  public Vertices []node;

  MyGraph(int size)
  {
    //set value
    this.size = size;
    result = 1;
    node = new Vertices[size];

  }

  //set initial node value
  public void setData()
  {
    if(node == null)
    {
      Console.WriteLine("\nEmpty Graph");
    }else
    {
      for(int index = 0; index < size; index++)
      {
        // avoid java.lang.nullPointerException
        node[index]=new Vertices(); 
        node[index].data=index;//set your data
        node[index].next=null;
      }
    }
  }
  //connect two nodes
  public void connect(int start,int end)
  {
    AjlistNode newEdge=new AjlistNode();
    newEdge.id=end;//end node
    newEdge.next=null;
    if(node[start].next==null)
    {
      node[start].next=newEdge;
    }else
    {
      AjlistNode temp=node[start].next;

      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=newEdge;
    }
  }
  //Add edge at the end
  public void addEdge(int start,int end)
  {
    if(start < size && end < size && node != null)
    {
      connect(start,end);

    }else{
      Console.WriteLine("\nEmpty Graph");
    }
  }

  public void printGraph()
  {

    if(size>0 && node!=null)
    {
      for(int index=0;index < size;index++)
      {
        Console.Write("\nAdjacency list of vertex "+index+" :");

        AjlistNode temp=node[index].next;

        while(temp!=null)
        {
          Console.Write("  "+node[temp.id].data);

          temp=temp.next;
        }
      }
    }
  }
  //This function are capable to count all path between two nodes
  public void  count_path(int start,int end,Boolean []visit)
  {
    if(start >size 
      || end >size 
      || start<0 
      || end<0 
      || node==null)
    {
      //invalid node location
      return ;
    }
    if(visit[start]==true)
    {
      //node is already visited
      return;
    }
    if(start==end)
    {
      //when source and destination are get
      result=result+1;
    }
    //active the visiting node status
    visit[start]=true;
    AjlistNode  temp=node[start].next;
    while(temp!=null)
    {
      //check node by edges
      count_path(temp.id,end,visit); 
      temp=temp.next;
    }
    //inactive current visiting node status
    visit[start]=false;
  }

  public void  total_path(int source,int destination)
  {
    //for resultant paths
    result=0;
    Boolean []visit=new Boolean[size];
    for(int i=0;i<size;i++)
    {
      visit[i]=false;
    }
    count_path(source,destination,visit);
    Console.WriteLine("\n Possible Path : "+result);
  }

  public static void Main(String[] args) 
  {
    int totalNode=6;

    MyGraph g=new MyGraph(totalNode);

    g.setData();

    //Connected two node with Edges
    g.addEdge(0, 1); 
    g.addEdge(0, 3); 
    g.addEdge(1, 2); 
    g.addEdge(1, 4); 
    g.addEdge(2, 3); 
    g.addEdge(2, 4); 
    g.addEdge(2, 5); 
    g.addEdge(3, 1); 
    g.addEdge(3, 5); 
    g.addEdge(5, 4); 

    g.printGraph();

    //value 0 is source node
    int source = 0;
    //value 4 is destination node
    int destination = 4;

    g.total_path(source,destination);

  }
}

Output

Adjacency list of vertex 0 :  1  3
Adjacency list of vertex 1 :  2  4
Adjacency list of vertex 2 :  3  4  5
Adjacency list of vertex 3 :  1  5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 :  4
 Possible Path : 8
<?php 
/*
* PHP Program 
//Count all possible paths between two vertices
*/

class AjlistNode
{
  public $vId;
  public $next;
  function __construct($vId)
  {
    $this->vId=$vId;
    $this->next=NULL;
  }
}
class Node
{
  public $data;
  public $next;
  function __construct($data)
  {
    $this->data=$data;
    $this->next=NULL;

  }
}
class MyGraph
{

  public $node;
  public $size;
  function __construct($size)
  {
    $this->size=$size;
    $this->node=[];  //empty array
  }
  public function setData()
  {
    if($this->size>0)
    {
      for($index=0;$index<$this->size;$index++)
      {
        $this->node[$index]=new Node($index);
      }

    }
  }
  public function connect($start,$end)
  {
    $newEdge=new AjlistNode($end);
    if($this->node[$start]->next==NULL)
    {
      $this->node[$start]->next=$newEdge;
    }
    else
    {

      $temp=$this->node[$start]->next;
      while($temp->next!=NULL)
      {
        $temp=$temp->next;
      }
      $temp->next= $newEdge;
    }
  }
  public function addEdge($start,$end)
  {
    if($this->size > $start && $this->size>$end)
    {
      $this->connect($start,$end);
    }
    else
    {
      echo "\n Invalid node";
    }
  }
  public function printGraph()
  {
    if($this->size>0 && count($this->node)>0 && $this->node!=NULL)
    {
      for($index=0;$index<$this->size;$index++)
      {
        echo ("\nAdjacency list of vertex ".$index." : ");
        $temp=$this->node[$index]->next;
        while($temp!=NULL)
        {
          echo ("  ".$this->node[$temp->vId]->data);
          $temp=$temp->next;
        }
      }
    }
  }




  
//This function are capable to count all path between two nodes
  public function count_path($start,
    $end,
    &$visit,
    &$result)
  {
    if($start>$this->size 
      || $end>$this->size 
      || $start<0 
      || $end<0 
    )
    {
      //invalid node location
      return ;
    }
    if($visit[$start]==true)
    {
      //node is already visited
      return;
    }
    if($start==$end)
    {
      //when source and destination are get
      $result=($result)+1;
    }
    //active the visiting node status
    $visit[$start]=true;
    $temp= $this->node[$start]->next;
    while($temp!=NULL)
    {
      //check node by edges
      $this->count_path($temp->vId,$end,$visit,$result); 
      $temp=$temp->next;
    }
    //inactive current visiting node status
    $visit[$start]=false;
  }
  
  public function total_path($source,$destination)
  {
   //for resultant paths
   $result=0;
   $visit= array_fill(0, $this->size, false);
   $this->count_path($source,$destination,$visit,$result);
   echo "\n Possible Path : ".$result."\n";
 }

}


function main()
{
    //create object
  $g=new MyGraph(6);
  $g->setData();

  //Connected two node with Edges
  $g->addEdge(0,1); 
  $g->addEdge(0,3); 
  $g->addEdge(1,2); 
  $g->addEdge(1,4); 
  $g->addEdge(2,3); 
  $g->addEdge(2,4); 
  $g->addEdge(2,5); 
  $g->addEdge(3,1); 
  $g->addEdge(3,5); 
  $g->addEdge(5,4); 

  $g->printGraph();
  
  //value 0 is source node
  $source=0;
  //value 4 is destination node
  $destination=4;
  
  $g->total_path($source,$destination);

}
main();
?>

Output

Adjacency list of vertex 0 :   1  3
Adjacency list of vertex 1 :   2  4
Adjacency list of vertex 2 :   3  4  5
Adjacency list of vertex 3 :   1  5
Adjacency list of vertex 4 : 
Adjacency list of vertex 5 :   4
 Possible Path : 8
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment