Warshall’s Algorithm

Transitive Closure and shortest path between every pair of vertices.

Transitive Closure

Transitive closure shows if there is a path between any two nodes,i.e if one node is reachable to another via any possible path.

The transitive closure of a directed graph with n vertices can be defined as the n-by-n boolean matrix T, in which the element in the ith row and jth column is 1 if there exist a directed path from the ith vertex to the jth vertex, otherwise it is zero.

In Warshall’s algorithm, we construct a sequence of Boolean matrices A =W⁰, W¹, W², W³, …, W^n =T, where A and T are as above.

This can be done from digraph D as follows. W¹[ i],[ j] = 1 if and only if there is a walk from i v to j v with elements of a subset of {v 1 }as interior vertices. W² [i][ j] = 1 if and only if there is a walk from ] i v to j v with elements of a subset of {v 1 , v 2 } as interior vertices.

Continuing this process, we generalize to W ^k[i ][j] = 1 if and only if there is a walk from i v to j v with elements of a subset of { v 1 , v 2 , …, v k } as interior vertices.

Algorithm Warshall

It uses Dynamic programming.The kth matrix depends on k-1 th matrix. Recurrence relating elements R(k) to elements of R(k-1) is: R(k) [i,j] = R(k-1)[i,j] or (R(k-1)[i,k] and R(k-1)[k,j]).

The time complexity of this algorithm is O(n³).

Floyd Warshall Algorithm

This algorithm is used on edge-weighted di-graphs. It is used to find the shortest path between any two vertices.it has the same idea as above.

On the kth iteration, the algorithm determines shortest paths between every pair of vertices i, j that use only vertices among 1,…,k as intermediate

D(k) [i,j] = min {D(k-1)[i,j], D(k-1)[i,k] + D(k-1)[k,j]}

The adjacency weight matrix is made with the following rules:

1}if i is equal to j W[i][j]=0

2}the weight between the vertices are saved as it is.

3} remaining is filled with infinity

Time complexity =0(n³)