Floyds and Warshalls
Floyds and Warshalls
Floyds and Warshalls
algorithm.
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int iN, i, j, k;
int iaFloyd[10][10], iaCost[10][10];
printf("n*********************************************************");
printf("n*tPROGRAM TO IMPLEMENT FLOYD'S ALGORITHMt*n");
printf("*********************************************************");
printf("nEnter the number of verticesn");
scanf("%d",&iN);
printf("nEnter the Cost adjacency Matrixn");
for(i=0;i<iN;i++)
for(j=0;j<iN;j++)
scanf("%d",&iaCost[i][j]);
printf("nInput Graphn");
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
printf("%dt",iaCost[i][j]);
}
printf("n");
}
printf("n");
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
iaFloyd[i][j] = iaCost[i][j];
}
}
for(k=0;k<iN;k++)
{
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
if(iaFloyd[i][j] > (iaFloyd[i][k] + iaFloyd[k][j]))
iaFloyd[i][j] = (iaFloyd[i][k] + iaFloyd[k][j]);
}
}
}
printf("nAll Pair Shortest Path Matrixn");
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
printf("%dt",iaFloyd[i][j]);
}
printf("n");
}
printf("n");
return 0;
}
Output
0 3 9999 7 9
3 0 4 2 9999
9999 4 0 5 6
72504
9 9999 6 4 0
Input Graph
0 3 9999 7 9
3 0 4 2 9999
9999 4 0 5 6
7 2 5 0 4
9 9999 6 4 0
All Pair Shortest Path Matrix
0 3 7 5 9
3 0 4 2 6
7 4 0 5 6
5 2 5 0 4
9 6 6 4 0
b) Design and implement C/C++ Program to find the transitive closure using Warshal’s algorithm.
#include <stdio.h>
const int MAX = 100;
void WarshallTransitiveClosure(int graph[MAX][MAX], int numVert);
int main(void)
{
int i, j, numVert;
int graph[MAX][MAX];
printf("Warshall's Transitive Closure");
printf("Enter the number of vertices : ");
scanf("%d",&numVert);
printf("Enter the adjacency matrix :-n");
for (i=0; i<numVert; i++)
for (j=0; j<numVert; j++)
scanf("%d",&graph[i][j]);
WarshallTransitiveClosure(graph, numVert);
printf("nThe transitive closure for the given graph is :-n");
for (i=0; i<numVert; i++)
{
for (j=0; j<numVert; j++)
{
printf("%dt",graph[i][j]);
}
printf("n");
}
return 0;
}
void WarshallTransitiveClosure(int graph[MAX][MAX], int numVert)
{
int i,j,k;
for (k=0; k<numVert; k++)
{
for (i=0; i<numVert; i++)
{
for (j=0; j<numVert; j++)
{
if (graph[i][j] || (graph[i][k] && graph[k][j]))
graph[i][j] = 1;
}
}
}
}
Output
/***************************************
***************************************/
0010
0001
1000
0100
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
/***************************************
***************************************/
0110
1001
1001
0110
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1