/*ALL PAIR SHORTEST PATH*/
#include<conio.h>
#include<stdio.h>
void main()
{
int wt[10][10],n,i,j;
void Floyd_shortest_path(int matrix[10][10],int n);
clrscr();
printf("\n Create a graph using Adjacency Matrix");
printf("\n\n How many vertices are there ?");
scanf("%d",&n);
printf("\nEnter The Elements");
printf("[Enter 999 as infinity value]");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("\nwt[%d][%d]",i,j);
scanf("%d",&wt[i][j]);
}
}
printf("\n\tComputing All pair shortest path...\n");
Floyd_shortest_path(wt,n);
getch();
}
void Floyd_shortest_path(int wt[10][10],int n)
{
int D[5][10][10],i,j,k;
int min(int,int);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
D[0][i][j]=wt[i][j];
}
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
D[k][i][j]=min(D[k-1][i][j],(D[k-1][i][k]+D[k-1][k][j]));
}
}
}
for(k=1;k<=n;k++)
{
printf("\nD(%d)=\n",k);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",D[k][i][j]);
}
printf("\n");
}
}
}
int min(int a,int b)
{
if(a<b)
return a;
else
return b;
}
OUTPUT:
Create a graph using Adjacency Matrix
How many vertices are there ?4
Enter The Elements[Enter 999 as infinity value]
wt[1][1]0
wt[1][2]999
wt[1][3]3
wt[1][4]999
wt[2][1]2
wt[2][2]0
wt[2][3]999
wt[2][4]999
wt[3][1]999
wt[3][2]7
wt[3][3]0
wt[3][4]1
wt[4][1]6
wt[4][2]999
wt[4][3]999
wt[4][4]0
Computing All pair shortest path...
D(1)=
0 999 3 999
2 0 5 999
999 7 0 1
6 999 9 0
D(2)=
0 999 3 999
2 0 5 999
9 7 0 1
6 999 9 0
D(3)=
0 10 3 4
2 0 5 6
9 7 0 1
6 16 9 0
D(4)=
0 10 3 4
2 0 5 6
7 7 0 1
6 16 9 0
#include<conio.h>
#include<stdio.h>
void main()
{
int wt[10][10],n,i,j;
void Floyd_shortest_path(int matrix[10][10],int n);
clrscr();
printf("\n Create a graph using Adjacency Matrix");
printf("\n\n How many vertices are there ?");
scanf("%d",&n);
printf("\nEnter The Elements");
printf("[Enter 999 as infinity value]");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("\nwt[%d][%d]",i,j);
scanf("%d",&wt[i][j]);
}
}
printf("\n\tComputing All pair shortest path...\n");
Floyd_shortest_path(wt,n);
getch();
}
void Floyd_shortest_path(int wt[10][10],int n)
{
int D[5][10][10],i,j,k;
int min(int,int);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
D[0][i][j]=wt[i][j];
}
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
D[k][i][j]=min(D[k-1][i][j],(D[k-1][i][k]+D[k-1][k][j]));
}
}
}
for(k=1;k<=n;k++)
{
printf("\nD(%d)=\n",k);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",D[k][i][j]);
}
printf("\n");
}
}
}
int min(int a,int b)
{
if(a<b)
return a;
else
return b;
}
OUTPUT:
Create a graph using Adjacency Matrix
How many vertices are there ?4
Enter The Elements[Enter 999 as infinity value]
wt[1][1]0
wt[1][2]999
wt[1][3]3
wt[1][4]999
wt[2][1]2
wt[2][2]0
wt[2][3]999
wt[2][4]999
wt[3][1]999
wt[3][2]7
wt[3][3]0
wt[3][4]1
wt[4][1]6
wt[4][2]999
wt[4][3]999
wt[4][4]0
Computing All pair shortest path...
D(1)=
0 999 3 999
2 0 5 999
999 7 0 1
6 999 9 0
D(2)=
0 999 3 999
2 0 5 999
9 7 0 1
6 999 9 0
D(3)=
0 10 3 4
2 0 5 6
9 7 0 1
6 16 9 0
D(4)=
0 10 3 4
2 0 5 6
7 7 0 1
6 16 9 0
No comments:
Post a Comment