c programming adjacency matrices paths

Question

How do I find if there is a path from index1 to index2 in given adjacency matrix?
Do I need to use recursion?

This is my code:

int path(int adj_mat[][N], int*pindex1, int *pindex2)
{       
  int i=0;       //column
  int yes=0;     //flag
  int j;      
  for(i;i<N;i++)
  {
      if(adj_mat[i][*pindex2-1]==1)
      {
          if(i==*pindex1-1)
              yes=1;
          for(j=i-1; j<0;--j)
          {
              if(adj_mat[j][i]==1)
                  if(j==*pindex1-1)
                      yes=1;
          }                 
      }
  }

  return yes;
}

I can't think of an algorithm that needs recursion, but there are some where recursion helps. You don't need to use recursion at all. </pedant> — Skizz

pandaboy pandaboy · Accepted Answer · 2015-04-24T11:42:34

I think your adjacency matrix got 0 and 1 as values. In your case 0 means that no path exist between index1 and index2 and 1 means that it exists.

so for a given matrix like this:

 0 | 0 | 0
-----------
 0 | 1 | 0
-----------
 0 | 0 | 0

there would only exist one path from index1 = 1 to index2 = 1:

matrix[1][1] = 1 => a path exists
matrix[0][1] = 0 => a path does not exist

So you just need to return the content and check it...:

return adj_mat[*pindex1][*pindex2];

c programming adjacency matrices paths

1 Answers