DAA-algorithms/warshall.cpp at main · mudit2004/DAA-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<iomanip>
#define MAX 20
#define INF 99999
#define NIL -1
using namespace std;
void FloydWharshal(int Cost[][MAX],int D[][MAX],int P[][MAX],int n)
{
	int i,j,k;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
		D[i][j] = Cost[i][j];
		if(D[i][j]==0 || D[i][j]==INF)
			P[i][j] = NIL;
		else
		    P[i][j] = i;
		}
	}
	for(k=1;k<=n;k++)
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
			if(D[i][k]+D[k][j] < D[i][j] )
				{
			    D[i][j] = D[i][k]+D[k][j];
			    P[i][j] = P[k][j];
			    }
			}
		}
	}

}
int main()
{
 int n;
 int i,j;

 //Test Input-1
 n=5;
 //Cost Matrix for the input graph
 int Cost[][MAX]={ {0,0,0,0,0,0},
      {0,0,3,8,INF,-4},
      {0,INF,0,INF,1,7},
      {0,INF,4,0,INF,INF},
      {0,2,INF,-5,0,INF},
      {0,INF,INF,INF,6,0} };

 int Dist[MAX][MAX];
 int Parent[MAX][MAX];
 FloydWharshal(Cost,Dist,Parent,n);
 cout<<"\n\nDistance Matrix: ";
 for(i=1;i<=n;i++)
 {
  cout<<"\n";
  for(j=1;j<=n;j++)
  {
   if(Dist[i][j]==INF)
    cout<<"INF\t\t";
   else
    cout<<Dist[i][j]<<"\t\t";
  }
 }
 cout<<"\n\nParent Matrix: ";
 for(i=1;i<=n;i++)
 {
  cout<<"\n";
  for(j=1;j<=n;j++)
  {
   if(Parent[i][j]==NIL)
    cout<<"NIL\t\t";
   else
    cout<<Parent[i][j]<<"\t\t";
  }
 }

}