Computer Science: 5th sem ADA Lab Program 13

Analysis and Design of Algorithms Lab.

Question 13.

//Implement floyd's algorithm for the all-pairs-shortest-path problem.
//Compute the transitive closure of a given directed graph using warshall's
#include <iostream>
#include <conio.h>
#define MAX 10

using namespace std;

void disp(int arr[MAX][MAX],int n)
{
for(int i=0;i<n;i++)
{
cout<<"\n";
for(int j=0;j<n;j++)
cout<<arr[i][j]<<" ";
}
}
void inp(int arr[MAX][MAX],int n)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>arr[i][j];
}

inline int min(int a,int b)
{
return a<b?a:b;
}

void floyd(int graph[MAX][MAX],int n)
{
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
}

void warshal(int graph[MAX][MAX],int n)
{
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
graph[i][j]=graph[i][j] || (graph[i][k] && graph[k][j]);
}

void main()
{
cout<<"\nWarshal's:\nEnter the size for matrix:";
int n;cin>>n;
int graph[MAX][MAX];
inp(graph,n);
warshal(graph,n);
cout<<"\nWarshal's output:\n";
disp(graph,n);

cout<<"\nFloyd's:\nEnter the size for matrix:";
cin>>n;
int weighted_graph[MAX][MAX];
inp(weighted_graph,n);
floyd(weighted_graph,n);
cout<<"\nFloyd's's output:\n";
disp(weighted_graph,n);

getch();
}