Experiment No: 9
1. Experiment vision:Write a program
to study and implement Floyd’s algorithm.
2. OBJECTIVE: Program
for computing all pairs shortest path.
3. THEORY:
Used to find
shortest paths in a weighted graph
• Travel maps containing driving distance from
one point to another – Represented by tables – Shortest distance from point A
to point B given by intersection of row and column – Route may pass through
other cities represented in the table
• Navigation systems
All-pairs shortest-path problem • Graph G = (V, E) • Weighted and directed
graph
• Problem: Find
the length of the shortest path between every pair of vertices – Length of the
path is strictly determined by the weight of its edges – It is not based on the
number of edges traversed
4. PROGRAM:
#include<stdio.h>
#include<conio.h>
int min(int,int);
void floyds(int p[10][10],int n)
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
p[i][j]=0;
else
p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}
int min(int a,int b)
{
if(a<b)
return(a);
else
return(b);
}
void main()
{
int p[10][10],w,n,e,u,v,i,j;;
clrscr();
printf("\n Enter the
number of vertices:");
scanf("%d",&n);
printf("\n Enter the number
of edges:\n");
scanf("%d",&e);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
p[i][j]=999;
}
for(i=1;i<=e;i++)
{
printf("\n Enter the
end vertices of edge%d with its weight \n",i);
scanf("%d%d%d",&u,&v,&w);
p[u][v]=w;
}
printf("\n Matrix of input
data:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d
\t",p[i][j]);
printf("\n");
}
floyds(p,n);
printf("\n Transitive
closure:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d
\t",p[i][j]);
printf("\n");
}
printf("\n The shortest
paths are:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j)
printf("\n
<%d,%d>=%d",i,j,p[i][j]);
}
getch();
}
5. OUTPUT:
------------------------------------------
------------------------------------------
6. conclusion:
Thus a
C program for Floyd’s algorithm has been implemented
and executed successfully.
8. Discussion Questions:
1) what is Floyd’s algorithm?
_________________________________________________________________________________________________________________________________________________________
2) Briefly give the difference between Floyd’s
algorithm and Warshall algorithm.
________________________________________________________________________________________________________________________________________________________
No comments:
Post a Comment