Floyds and Warshalls

Download as pdf or txt
Download as pdf or txt
You are on page 1of 5

Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem using Floyd’s

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

Enter the number of vertices

Enter the Cost adjacency Matrix

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

/***************************************

Warshall's Transitive Closure

***************************************/

Enter the number of vertices : 4

Enter the adjacency matrix :-

0010

0001

1000

0100

The transitive closure for the given graph is :-

1 0 1 0

0 1 0 1
1 0 1 0

0 1 0 1

/***************************************

Warshall's Transitive Closure

***************************************/

Enter the number of vertices : 4

Enter the adjacency matrix :-

0110

1001

1001

0110

The transitive closure for the given graph is :-

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

You might also like