Q13Discrete Mathematics

Warshall's Algorithm is a highly efficient dynamic programming technique used to compute the Transitive Closure of a directed graph (or a mathematical relation). The transitive closure fundamentally answers the question of reachability: is there ANY path, of any length, from vertex $i$ to vertex $j$? The algorithm operates by iteratively constructing a sequence of Boolean matrices, $W_0,W_1,dots,W_n$.

Step 1: Construct the Initial Matrix $W_0$

The initial relation is $R=\{(a,a),(a,b),(a,d),(c,b),(c,c),(d,b),(d,c),(d,d)\}$. We define the vertices $a=1,b=2,c=3,d=4$. We construct the initial Boolean adjacency matrix $W_0$, where $W_0[i][j]=1$ if there is a direct edge from $i$ to $j$, and 0 otherwise.

a b c d a [ 1 1 0 1 ] b [ 0 0 0 0 ] c [ 0 1 1 0 ] d [ 0 1 1 1 ] This is our $W_0$ matrix.

Step 2: Iterative Matrix Computation

The core formula is: $W_k[i][j]=W_{k-1}[i][j]\vee (W_{k-1}[i][k]\wedge W_{k-1}[k][j])$. This mathematically means a path exists from $i$ to $j$ allowing intermediate vertices up to $k$, IF a path already existed, OR if a path exists from $i$ to $k$ AND a path exists from $k$ to $j$.

Iteration 1 ($k=1$, vertex 'a'): We evaluate if routing through vertex 'a' creates new paths. Looking at $W_0$, column 'a' (inputs to 'a') only has a 1 at row 'a'. Routing 'a' through 'a' yields no new information. $W_1$ remains strictly identical to $W_0$.

Iteration 2 ($k=2$, vertex 'b'): We evaluate routing through vertex 'b'. Looking at $W_1$, row 'b' (outputs from 'b') is entirely 0. Vertex 'b' is a dead end. Routing through it is impossible. $W_2$ remains strictly identical to $W_1$.

Iteration 3 ($k=3$, vertex 'c'): We evaluate routing through vertex 'c'. Inputs to 'c' (Column 3 in $W_2$): row 'c' (3) and row 'd' (4). Outputs from 'c' (Row 3 in $W_2$): column 'b' (2) and column 'c' (3). New paths formed by combining these: - Path $d\to c\to b$ creates a new connection $d\to b$. However, $W_2[4][2]$ is already 1. No new 1s are generated. $W_3$ remains strictly identical to $W_2$.

Iteration 4 ($k=4$, vertex 'd'): We evaluate routing through vertex 'd'. Inputs to 'd' (Column 4 in $W_3$): row 'a' (1) and row 'd' (4). Outputs from 'd' (Row 4 in $W_3$): column 'b' (2), column 'c' (3), column 'd' (4). New paths formed: - Path $a\to d\to b$ creates connection $a\to b$ (already 1). - Path $a\to d\to c$ creates connection $a\to c$. $W_3[1][3]$ was 0. It now becomes 1! - Path $a\to d\to d$ creates connection $a\to d$ (already 1).

Final Transitive Closure Matrix $W_4$

Updating the matrix with the newly discovered path ($a\to c$): a b c d a [ 1 1 1 1 ] b [ 0 0 0 0 ] c [ 0 1 1 0 ] d [ 0 1 1 1 ]

This final matrix definitively represents the Transitive Closure of the relation.