Warshalls Algorithm

#programming #algorithms #graphs

A formal algorithm to construct the Transitive Closure of a graph $G$.
It does not matter if the graph is directed.
For information on graphs, read Graphs

Warshall's algorithm is simply a boolean mask to represent whether an edge exists between $u$ and $v$. Since an adjacency matrix can also be interpreted as having direction, it serves as the basis for creation of transitive closure in either of the cases

We start with $T$, a copy of the adjacency matrix, which we will modify to represent the transitive closure

Core Idea

We progressively allow intermediate vertices.

So we define

After step $k$, {cpp}T[i][j] = 1 if there is a path from $i$ to $j$ using only vertices from $\{1,2,\dots ,k\}$ as intermediates

Essentially, we ask

Does going through vertex $k$ connect $i$ and $j$?

Relation

At step $k$, for each pair $i,j$
We do

T[i][j] = T[i][j] || (T[i][k] && T[k][j]); 

Pseudo code

Initialize T = adjacency matrix

for k = 1 to n:
    for i = 1 to n:
        for j = 1 to n:
            T[i][j] = T[i][j] OR (T[i][k] AND T[k][j])

Time complexity : $O(n^3)$

Floyd-Warshalls Algorithm