Hi,
I have written a code to generate random graphs and test floyd warshalls algorithm. but the output of the adjacency matrix is wearied. Could you please help me in correcting it? Below is the code.
Code:
/*C PROGRAM TO IMPLEMENT ALL PAIR SHORTEST PATH USING FLOYDS ALGORITHM
INPUT: N VALUE FOR NUMBER OF VERTICES
OUTPUT: ADJACENCY MATRIX
SHORTEST DISTANCE MATRIX
*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define INF 99999
#define MAX_NODE 50
#define MAX_EDGE 50
void AdjacencyMatrix(int a[][MAX_NODE],int n, int e){ //To generate adjacency matrix for given nodes
int i,j;
srand ( time(NULL) );
for(i = 0;i < n; i++)
{
for(j = 0;j <= e; j++)
{
a[i][j] = 0;
}
}
for(i = 1; i < n; i++)
{
for(j=0;j<i;j++)
{
a[i][j] = 99;
a[j][i] = rand()%10;
}
}
}
int min(int a,int b){
if(a < b)
return a;
else
return b;
}
void floyds(int a[][],int n,int e){
int i,j,k;
for(k = 0;k < n ; k++)
{
for(i = 0;i < n; i++)
{
for(j = 0;j < e ; j++)
{
a[i][j] = min (a[i][j], a[i][k] + a[k][j] );
}
}
}
}
int main()
{
int a[MAX_NODE][MAX_EDGE],n,i,j,e;
/*
FILE *fp = fopen("floyds.dot","w");
fprintf(fp,"digraph A {\n");
*/
/*printf("Enter the vertices of the digraph\n");
/* scanf("%d",&n); */
srand ( time(NULL) );
n = rand()%MAX_NODE;
printf("vertices of the digraph is: %d \n", n);
srand ( time(NULL) );
e = rand()%MAX_EDGE;
if(n == e) {
n = n+1;
}
printf("Edges of the digraph is: %d \n", e);
AdjacencyMatrix(a,n,e);
printf("\t\tAdjacency Matrix of the graph\n"); /* PRINT ADJACENCY MATRIX */
for(i = 0;i < n; i++)
{
for(j = 0;j < e; j++)
{
printf("%d->%d = %d\t", i, j, a[i][j]); /* printf("%d\t", a[i][j]); */
}
printf("\n");
}
floyds(a,n,e);
printf("\n Shortest distance matrix\n"); /*PRINT SHORTEST DISTANCE MATRIX*/
for(i = 0;i < n; i++)
{
for(j = 0;j < e; j++)
{
if (a[i][j] == 99)
printf("%7s", "99");
else
printf ("%7d", a[i][j]);
}
printf("\n");
}
return 0;
}