0% found this document useful (0 votes)
3 views6 pages

ADA Pgm 3 and 4

The document outlines the implementation of three algorithms in C/C++: Floyd's algorithm for solving the All-Pairs Shortest Paths problem, Warshall's algorithm for finding the transitive closure of a directed graph, and Dijkstra's algorithm for finding the shortest paths from a given vertex in a weighted connected graph. Each algorithm includes a description, pseudocode, and a sample program with input and output examples. The programs utilize adjacency matrices to represent graphs and compute shortest paths or transitive closures based on the specified algorithms.
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
3 views6 pages

ADA Pgm 3 and 4

The document outlines the implementation of three algorithms in C/C++: Floyd's algorithm for solving the All-Pairs Shortest Paths problem, Warshall's algorithm for finding the transitive closure of a directed graph, and Dijkstra's algorithm for finding the shortest paths from a given vertex in a weighted connected graph. Each algorithm includes a description, pseudocode, and a sample program with input and output examples. The programs utilize adjacency matrices to represent graphs and compute shortest paths or transitive closures based on the specified algorithms.
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Program 3

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

int min(int a,int b)


{
return(a<b) ? a : b;
}

void floyd(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] = min(p[i][j], p[i][k] + p[k][j]);
}

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:

Enter the n value: 4

Enter the graph data:


0 999 3 999
2 0 999 999
999 7 0 1
6 999 999 0

Shortest path matrix


0 10 3 4
2056
7701
6 16 9 0

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:

Enter the n value: 4

Enter the graph data:


0100
0001
0000
1010

Resultant path matrix


1111
1111
0000
1111
Program 4
Design and implement C/C++ Program to find shortest paths from a given vertex in a
weighted connected graph to other vertices using Dijkstra's algorithm.

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

Enter the graph data:


0 15 10 999 45 999
999 0 15 999 20 999
20 999 0 20 999 999
999 10 999 0 35 999
999 999 999 30 0 999
999 999 999 4 999 0

Enter the souce node: 2

Shortest distance from 2 to 1 is 35


Shortest distance from 2 to 2 is 0
Shortest distance from 2 to 3 is 15
Shortest distance from 2 to 4 is 35
Shortest distance from 2 to 5 is 20
Shortest distance from 2 to 6 is 999

Output 2:
enter the no. of nodes:

enter the cost adjacency matrix,'9999' for no direct path

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

enter the starting vertex:


6

Shortest path from starting vertex to other vertices are

6->1=49
6->2=14
6->3=29
6->4=4
6->5=34
6->6=0

You might also like