# Warshall's algorithm multiple choice…

Here's a question given to us for practice.

Can anyone help me through the steps of solving it? The algorithm itself is confusing to read, so I'm just looking for a concise way to calculate $W_1$, $W_2$, etc. Are there any general rules that I should be aware of?

-

To eliminate the suspense, the answer is (B). How did I find it?

Warshall's algorithm produces what is known as the transitive closure of a relation, $R$ which is the smallest transitive relation $R^+$ which contains $R$. In functional terms, we start with $R$ and add just enough new elements to $R$ to make a transitive relation.

It's conceptually easier if we express $R$ as directed graph $G$ on $n$ vertices, as your problem does, and think of adding a directed edge between vertices $i$ and $j$ whenever we can get from $i$ to $j$ by passing through another vertex $k$. In other words, if we can get from $i$ to $j$ via $k$, we'll add a new edge bypassing $k$. We do this by computing a sequence of $n\times n$ matrices $W_0, W_1, \dots W_n$, where the final result, $W_n$, has entries

$$W_n[i, j] = \begin{cases} 1 & \text{if there is some directed path in the graph from i to j} \\ 0 & \text{if there is no way to get from vertex i to vertex j} \end{cases}$$

The algorithm is pretty simple; it computes $W_k$ from $W_{k-1}$, by doing the following:

for each pair of vertices (i, j)
set W_k[i, j] to W_{k-1}[i, j] OR (W_{k-1}[i, k] AND W_{k-1}[k, j])


At the start, $W_0$ is just the adjacency matrix of the graph, so for every pair of vertices $(i, j), W_0[i, j]$ is $1$ if there is a directed edge from $i$ to $j$ and is zero if there is no edge from $i$ to $j$. Initially, select an order on the vertices, $v_1, v_2, \dots , v_n$. In your problem the order specified was $v_1 = a, v_2=b, v_3=c, v_4=d$.

Now we fill in the $W_1$ matrix: Using the algorithm above, the $W_1$ matrix will be computed from the $W_0$ matrix and vertex $v_1$. The end result will be that the $[i, j]$ entry in the matrix will be 1 if there is a path directly from vertex $i$ to vertex $j$ OR there is a way to get from $i$ to $j$ by passing through $v_1$, namely, in your case if there is a $i\rightarrow a$ edge AND a $a\rightarrow j$ edge, which is just a wordier way of saying what the second line of the algorithm is doing.

The algorithm is trivial to implement on a computer, but how would you do it by hand? In this problem, we start with the $W_0$ matrix and the $a$ row, for the $a$-to-$i$ part and the $a$ column, where the $a$-to-$j$ entries reside. Here's the $W_0$ matrix with the $a$ row and the $a$ column in red:

$$\left[ \begin{array}{cccc} \color{#ff0000}{0} & \color{#ff0000}{0} & \color{#ff0000}{0} & \color{#ff0000}{1} \\ \color{#ff0000}{1} & 0 & 1 & 0 \\ \color{#ff0000}{1} & 0 & 0 & 1 \\ \color{#ff0000}{0} & 0 & 1 & 0 \\ \end{array} \right]$$ Because of the OR part of the second line in the algorithm, we know that the entries that are $1$ in the $W_0$ matrix will remain $1$ in the $W_1$ matrix, so let's do an example where one of the entries in the $W_0$ matrix is $0$, namely the $[b, d]$ entry in the second row, fourth column. We see that the $[b, a]$ entry (in the $a$ column) is $1$ and that the $[a, d]$ entry (in the $a$ row) is also $1$ so since $1\text{ AND }1=1$, we replace the $0$ in the $[b, d]$ entry with $1$, giving us $$\left[ \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right]$$ It turns out that this is the only entry that changes during this process, so we're done; we've computed $W_1$.

To get $W_2$ we do the same steps, only this time we use $W_1\text{ and }v_2$. In case you've forgotten, $v_2=b$, so we now highlight the $b$ row and the $b$ column. If you do the process for the nonzero entries in the $W_1$ matrix, you'll find that nothing changes, so $W_2$ is the same as $W_1$.

Repeating this process, with vertices $c$ and $d$ we find that $$W_3=\left[ \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ \end{array} \right]\qquad W_4=\left[ \begin{array}{cccc} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ \end{array} \right]$$ and $W_4$ is our final answer. $W_4[i, j] = 1$ if and only if there is a path from $i$ to $j$ directly or through some combination of vertices $a, b, c, d$, which is to say, if there's any way at all of getting from $i$ to $j$. In this example, we see that we can get from any of $a, c, d$ to any other, but there's no way to get from any vertex to $b$.

In in relational terms, we started with $$R=\{(a, d),(b, a), (b, d),(c, a),(c, d),(d, c)\}$$ and wound up with $$R^+=\{(a, a),(a,c),(a,d),(b, a),(b, c),(b, d),(c, a),(c,c),(c, d),(d,a),(d, c),(d,d)\}$$

-