Warshal's Alqonthrn
* It s used to find transi tive closre
dynamie prmgranming
The branAitive Can be
cloßure of a digraph with n verices
defined by n boolen mtrix in uhich the element mth
(th yow
where' osísn and jtheotumn osi<n is 5
there is a tmvial
tivial path from ith vertex to h vertex,
otherwike it D
Algerithm Warshal
7 input i Adjaceny matix of
Houtput : Transitive digraph
closure of digraph
Ro) A
for k: 1 to n do
for iz 4 to n do
tor í= 1 to n do
Ck-) (k-)
(R Ci,kJ and R CK,iJ)
reurn Ro)
Trating p mabik
A
1
Initalize the
K= No.o Intermediate vertices
2 2
K= o
R
(a, a)= 1 (a,b) 1
d
> (d,6)= 1
(ab) =1 (6,d)=1
() ’(a,d)-1
R
(6,d)= 1
(2)
R
No pair
c d
)
>(6,4):/
(6,d)=1 with ( d,a):)
(d,)=/->():)
Cdd 1 with
(4,d)=l >d, d=1
(4)
R
b
d
Proqyam
#include < stdioihs
(int p[][o1 int n)
Vofd warshall
int i,j,kj
tor ( k=l j k<=nj ktt)
<njitt)
foy ( (2 1 ,
(i-1; iKenj j+t) PCKJLJJ
for [J[k]4f
PLiJLD- PLIJJliJI|P
3
int main()
int alieJ [ie] n,, i)
Enter the no.of vertices"J;
Printt ("
/ \n
matrix :|»")
Printt ("\n Enter the
Adjaconty
for (i=1; ÍKen; itt)
for Gzl; 0<-n, itt)
Start ("%d", kaCiJjJ):
warshall(a,n);
sln;
Printt (" The Resultant path Matix
for li-1; i<-n;itt)
for (j=l;i K=n;0tt)
Printt (*%.d'", aciJ SJ);
Printt ("\n'))
yetun o)
