C/C++ Finding all paths between two vertex in unweighted & undirected graph using an adjacency matrix

Question

I'm trying to find all paths between a starting vertex and an ending vertex using an adjacency matrix. My graph is unweighted & undirected.

I was trying to follow this algorithm but, I got stuck at the for each part.

Algorithm:

procedure FindAllPaths(u, dest)
{
   push u to stack;
   if(u == dest)
   {
      print stack;
   }
   else
   {
      foreach v that is adjacent with u and not in stack now
      {
         FindAllPaths(v, dest);
      }
   }
   pop from stack;
}

My code:

void AdjacencyMatrix :: Find_All_Paths(int Origin, int Destination)
{
      /*
      MATRIX:
      0 1 0 1 1
      0 1 0 1 1
      0 0 0 1 0
      0 1 1 1 0
      1 1 0 1 1
      */
    //Push Origin to stack
    Push_Vertex.push(Origin);

    //Determine if Origin == Destination, if so, print the stack
    if(Origin == Destination)
    {
        while(!Push_Vertex.empty())
        {
            cout << Push_Vertex.top() << " ";
            Push_Vertex.pop();
        }//while
        cout << endl;
    }//if

    else

}//Find_All_Paths()

Answer 1

You need to iterate over the row corresponding to the current node to find the nodes adjacent to it. This depends a little bit on exactly how your adjacency matrix is implemented, but it looks something like this:

for(int v = 0; v < n; v++)
{
    if(adj[Origin][v] && !inStack[v])
    {
        Find_All_Paths(Origin, Destination);
    }
}

adj is your adjacency matrix, with adj[u][v] being true if there is an edge from u to v. inStack is a boolean array storing whether a vertex is in the stack to allow for fast checking. Initialize the array to false, and set the index corresponding to a vertex to be true when you insert it into the stack and false when you pop it off.

Complete code:

void AdjacencyMatrix :: Find_All_Paths(int Origin, int Destination)
{
    //Push Origin to stack
    Push_Vertex.push(Origin);
    inStack[Origin] = true;

    //Determine if Origin == Destination, if so, print the stack
    if(Origin == Destination)
    {
        while(!Push_Vertex.empty())
        {
            cout << Push_Vertex.top() << " ";
            Push_Vertex.pop();
        }//while
        cout << endl;
    }//if

    else
    {
        for(int v = 0; v < n; v++)
        {
            if(adj[Origin][v] && !inStack[v])
            {
                Find_All_Paths(Origin, Destination);
            }
        }
    }
    Push_vertex.pop();
    inStack[Origin] = false;

}//Find_All_Paths()