Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here's a question given to us for practice.

enter image description here

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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)\} $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.