Find Transitive Closure Using Floyd-Warshall Algorithm

Find Transitive Closure Using Floyd-Warshall Algorithm

• 1.
  1October 23, 2019 PresentedBy: Name: Rajib Kumar Roy ID No: 1907561 A Presentation on Find Transitive Closure Using Floyd-Warshall Algorithm
• 2.
   A vertexj is reachable from another matrix i for all matrix pairs(i, j) in the given graph.  Reachable (there is a path from vertex i to j).  Example: Set, A= {0,1,2,3} Relation, R = {(1,2),(2,3),(3,4)} (1,3) is the transitive closure which must belongs to R.  Obtained by repeatedly adding the new value using union operation with previous Relation. Transitive Closure 2
• 3.
   Main Idea: Supposetwo nodes 1 and 4 a path exists between two vertices 1, 4, if • there is an edge from 1 to 4; or • there is a path from 1 to 4 going through vertex 2; or • there is a path from 1 to 4 going through vertex 2 and/or 3; or • ... So, (1,4) is a transitive closure Warshall Algorithm 3
• 4.
   On thekth iteration the algorithm determine if a path exists between two vertices i,j using just vertices among 1,….,k allowed as intermediate path using just 1,….,k-1 path from i to k and from k to j using just 1,….,k-1 Warshall Algorithm 4
• 5.
   Algorithm tofind Transitive Closure Input: The given graph. Output: Transitive Closure matrix. TransitiveClosure { R(0) A //copy adjacency matrix into another matrix for k = 1 to n do for i = 1 to n do for j = 1 to n do R(k) [i,j] := R(k-1) [i,j] OR ( R(k-1)[i,k] AND R(k-1) [k,j]); } Warshall Algorithm : Transitive Closure 5
• 6.
   First considera Graph(G), a Set(A, contains 4 elements) and a Relation Set(R).  It’s respective Adjacency Matrix (𝑀 𝑅) is: Working Procedure 6
• 7.
   Fetching TransitiveClosure from 1st iteration Adjacency Matrix (𝑀 𝑅).  There is found two new element of (a,c) and (b,d).  Perform union operation between two new element and previous Relation.  The graph has got two new edge. Cont… 7
• 8.
   Adjacency Matrix(𝑀𝑅 2 ) by updating previous 𝑀 𝑅(2nd iteration).  there have paths of (a and c, b and d), that’s why value is updated from 0 to 1.  Lets see through Warshall Algorithm  There is a edge between a and c Cont… 8
• 9.
   Fetching TransitiveClosure from Adjacency Matrix (𝑀 𝑅 2 ).  Found a new element of (a,d)  Perform again union operation.  new edge of a to d Cont… 9
• 10.
   Update matrixin a repeating way.  Transitive closure from Adjacency Matrix (𝑀 𝑅 3 )  No new valus are found  So, Adjacency Matrix (𝑀 𝑅 3 ) is the Transitive Closure Matrix.  Going forward cause of new value. Cont… 10
• 11.
  INPUT OUTPUT Result 11
• 12.
   Time Complexity:ϴ(𝑛3) as there are 3 nested loops(i,j,k).  Space Complexity: Requires extra space for separate matrices for recording intermediate results of the algorithm. Complexity 12
• 13.
  Thank you