ADA Pgm 3 and 4
ADA Pgm 3 and 4
a. Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem
using Floyd's algorithm.
Algorithm:
Floyd’s Algorithm
Accept no .of vertices
Call graph function to read weighted graph // w(i,j)
Set D[ ] <- weighted graph matrix // get D {d(i,j)} for k=0
// If there is a cycle in graph, abort. How to find?
Repeat for k = 1 to n
Repeat for i = 1 to n
Repeat for j = 1 to n
D[i,j] = min {D[i,j], D[i,k] + D[k,j]}
Print D
Program
#include<stdio.h>
#include<conio.h>
#define INF 999
void main()
{
int a[10][10], n, i, j;
clrscr();
printf("\n Enter the n value:");
scanf("%d", &n);
printf("\n Enter the graph data:\n");
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d",&a[i][j]);
floyd(a, n);
printf("\n Shortest path matrix\n");
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
printf("%d ", a[i][j]);
printf("\n");
}
getch();
}
Output:
b. Design and implement C/C++ Program to find the transitive closure using Warshal's
algorithm.
Algorithm
//Input: Adjacency matrix of digraph
//Output: R, transitive closure of digraph
Accept no .of vertices
Call graph function to read directed graph
Set R[ ] <- digraph matrix // get R {r(i,j)} for k=0
Print digraph
Repeat for k = 1 to n
Repeat for i = 1 to n
Repeat for j = 1 to n
R(i,j) = 1 if
{rij(k-1) = 1 OR
rik(k-1) = 1 and rkj(k-1) = 1}
Print R
Program:
#include<stdio.h>
void warsh(int p[][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++)
p[i][j]=p[i][j] || p[i][k] && p[k][j];
}
int main()
{
int a[10][10],n,i,j;
printf("\nEnter the n value:");
scanf("%d",&n);
printf("\nEnter the graph data:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
warsh(a,n);
printf("\nResultant path matrix\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",a[i][j]);
printf("\n");
}
return 0;
}
Output:
Algorithm: Dijikstra(G,s)
//Dijikstra’s algorithm for single source shortest path
//input:A weighted connected graph with non negative weights and its vertex s
//output:The length dv of a shortest path from s to v and penultimate vertex pv for every
vertex v in V
Initialize(Q)
for every vertex v in V do
dv<-∞;Pv<-null
Insert(Q,v,dv)
Ds<-0; Decrease(Q,s,ds);VT<-ǿ
for i<- 0 to │V│-1 do
u*<-DeleteMin(Q)
VT<-VT U{u*}
For every vertex u in V-VT that is adjacent to u* do
If du*+w(u*,u)<du
du<- du*+w(u*,u); pu<-u*
Decrease(Q,u,du)
Program:
#include<stdio.h>
#define INF 999
void dijkstra(int c[10][10], int n, int s, int d[10])
{
int v[10],min,u,i,j;
for(i=1;i<=n;i++)
{
d[i]=c[s][i];
v[i]=0;
}
v[s]=1;
for(i=1;i<=n;i++)
{
min=INF;
for(j=1;j<=n;j++)
if(v[j]==0 && d[j]<min)
{
min=d[j];
u=j;
}
v[u]=1;
for(j=1;j<=n;j++)
if(v[j]==0 && (d[u]+c[u][j])<d[j])
d[j]=d[u]+c[u][j];
}
}
int main()
{
int c[10][10], d[10],i,j,s,sum,n;
printf("\nEnter n value:");
scanf("%d",&n);
printf("\enter the cost adjacency matrix, Enter '9999' if no direct path :\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&c[i][j]);
printf("\nEnter the souce node:");
scanf("%d",&s);
dijkstra(c,n,s,d);
for(i=1;i<=n;i++)
printf("\nShortest distance from %d to %d is %d",s,i,d[i]);
return 0;
}
Output 1:
Enter n value: 6
Output 2:
enter the no. of nodes:
0 15 10 9999 45 9999
9999 0 15 9999 20 9999
20 9999 0 20 9999 9999
9999 10 9999 0 35 9999
9999 9999 9999 30 0 9999
9999 9999 9999 4 9999 0
6->1=49
6->2=14
6->3=29
6->4=4
6->5=34
6->6=0