adjacency matrix

Question

Given an adjacency matrix of a graph and a positive integer n find the number of path of length n between two vertices, I don't know how to convert to programming?

Answer 1

Take A^n then read the appropriate entry.

If you want it more efficient for single vertices, do a random walker starting at first vertex for n iterations.

Answer 2

I'm assuming this is homework, so here's a hint. If you were given a pencil and paper, and a small adjacency matrix, how would you count the number of paths?

Answer 3

How about using Dijkstra's shortest path algorithm (DSPA)? Let the cost of each arc in the network be 1. Use DSPA to find the distance between two distinct vertices. If the length is n, you have found a path of interest. Loop over all pairs of vertices.

Answer 4

This is my coding, but I do not know how to find the number of path of length between two vertices.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#define TRUE 1
#define FALSE 0

void main()
{
   int x;            
   int y;
   int n;
   int l;
   int a;
   int b;
   int length;
   char vertex='a';
   int num[50][50];

   printf("enter the number of vertices : ");
   scanf("%d",&n);
   //int num[n][n];

   for(x=0;x<n;x++)
   {
    for(y=0;y<n;y++)
      {
        printf("[%c,%c] : ",vertex+x,vertex+y);
         scanf("%d",&num[x][y]);
       }
   }

        printf("\n");

        printf("Adjacency matrix :\n");
        for(x=0;x<n;x++)
        {
            for(y=0;y<n;y++)

                printf("%d\t",num[x][y]);
                printf("\n");

            }

         printf("Enter a positive integer for length: ");
         scanf("%d",&length);

         length=sqrt(length);

         printf("Multiplication matrix :\n");
      for(l=0;l<=length;l++)
      {
        for(x=0;x<n;x++)
        {
            for(y=0;y<n;y++)

                num[x][y]=(num[x][y])*(num[y][x]);
               num[x][y]= num[x][y]+ num[y][x];

            }
       }


        printf("\n");

        for(x=0;x<n;x++)
        {
            for(y=0;y<n;y++)

                printf("%d\t",num[x][y]);
                printf("\n");

            }

         printf("\nPlease insert your starting point: ");
         scanf("%d",&a);
         printf("\nPlease insert your ending point: ");
         scanf("%d",&b);

         a=x-1;
         b=y-1;

         //printf("\nThe number of path from %d to %d: %d",a,b,num[a][b]);
         printf("\nThe number of path from %d to %d: %d",a,b,num[a][b]);

   getch();
   //return 0;

}