## Saturday, May 18, 2013

### Implementation of Warshall's Algorithm in C++ with Source Codes

Warshall's algorithm is used to find the transitive closure of a graph. It's one of the efficient method to compute closure path that can be produced. Transitive closure is an important application in graph theory in computer science.
The following provides the source codes for implementing the Warshall's algorithm:

``````
//.............................USE OF WARSHALL'S ALGORITHM TO CREATE TRANSITIVE CLOSURE OF A GRAPH..........

#include<iostream>
#include<conio.h>

using namespace std;
const int num_nodes =10;

int main()
{
//..............................................................VARIABLE DECLARATION
int num_nodes,k,n;
char i,j,res,c;

cout<<"\n\t\t\t\t.............................................................................\n";
cout<<"\n\t\t\t\t\"USE OF WARSHALL'S ALGORITHM TO CREATE TRANSITIVE CLOSURE OF A GRAPH\"";
cout<<"\n\t\t\t\t.............................................................................\n";

cout<<"\n\tMaximum number of nodes in the graph :";cin>>n;
num_nodes = n;
cout<<"\n\n\tNODES ARE LABELED AS A,B,C,......\n\n";
cout<<"\nEnter 'y'for 'YES' and 'n' for 'NO' !!\n";

for(i=65;i<65+num_nodes;i++)
for(j=65;j<65+num_nodes;j++)
{
cout<<"\n\tIs there an EDGE from " <<i<<" to "<<j<<" ? ";cin>>res;
if(res=='y')
else
}

cout<<"\n\t\t\t   ";
for(i=0;i<num_nodes;i++){
c =65+i;
cout<<c<<" ";
}
cout<<"\n\n";
for(int i=0;i<num_nodes;i++)
{
c =65+i;
cout<<"\t\t\t"<<c<<"  ";
for(int j=0;j<num_nodes;j++)
cout<<"\n";
}

//...................................................................APPLYING WARSHALL'S ALGORITHM

for(int i=0;i<num_nodes;i++)
for(int j=0;j<num_nodes;j++)

for(int k=0;k<num_nodes;k++)
for(int i=0;i<num_nodes;i++)
if(path[i][k]==1)
for(int j=0;j<num_nodes;j++)
path[i][j]=path[i][j]||path[k][j];

for(int i=0;i<num_nodes;i++)
for(int j=0;j<num_nodes;j++)

//....................................................................DISPLAYING THE TRANSITIVE CLOSURE

cout<<"\n........................................Transitive Closure of the Graph:...................................\n";

cout<<"\n\t\t\t   ";
for(i=0;i<num_nodes;i++){
c =65+i;
cout<<c<<" ";
}
cout<<"\n\n";
for(int i=0;i<num_nodes;i++)
{

c =65+i;
cout<<"\t\t\t"<<c<<"  ";
for(int j=0;j<num_nodes;j++)
cout<<"\n";
}

//...................................................................END MAIN

getch();
return 0;

}

``````

#### 1 comment :

1. hi. where did the value 65 (used in creating the adjacency matrix) came from? thanks. :)