Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 5

A length-zero graph path starts and ends at the same vertex. Therefore $P_0$ is the Boolean identity matrix. A graph path of length at most one is either such a stationary graph path or one original directed edge:The logical disjunction is entrywise. Diagonal entries of $E$ may be false if there are no self-loops, but every diagonal entry of $P_1$ is true because the zero-length graph path is allowed.

A graph path of length at most $k+1$ either already has length at most $k$, or consists of a prefix of length at most $k$ followed by one edge. ThereforeThe forward implication follows by removing the final edge of a nonempty graph path. Conversely, concatenating the indicated prefix and edge gives a walk of length at most $k+1$, and removing repetitions if necessary gives a graph path no longer than that walk.

Writing $\odot$ for Boolean matrix multiplication, the formula is $P_{k+1}=P_k\vee (P_k\odot E)$. Because $P_1$ includes the identity matrix, an equivalent formula isCompute each new matrix from an unchanged copy of the preceding matrix, so the subscript continues to specify exactly the length bound.

Start with $P_1=I\vee E$ and repeatedly apply part (b), keeping a fresh output matrix. A simple implementation is

P := I OR E
repeat:
    Q := P OR boolean_product(P, E)
    if Q = P: return P
    P := Q

At the start of each iteration, $P=P_k$ for the current length bound $k$. The update produces $P_{k+1}$, proving the loop invariant by mathematical induction. If $Q=P$, every edge extension of a known graph path is already known. Repeating the same update then makes no further change, so every longer graph path is represented as well.

Every reachable pair of distinct vertices has a simple path of at most $n-1$ edges: a repeated vertex allows the intervening part to be deleted. Thus the process stabilizes after finitely many updates and returnsThis is the reflexive transitive closure. An alternative stopping rule is to stop once the length bound is at least $n-1$, avoiding a final equality-detection iteration. For $n=0$ or $1$, $P_1$ already suffices.

Interpret the source's $m$ as the maximum finite shortest-path distance among reachable pairs, taking $m=0$ when only length-zero graph paths are needed. This is the length bound required for reflexive transitive closure. A directed graph cycle permits arbitrarily long walks, so the maximum length of all possible walks would not be a finite termination parameter.^[ref]

For the elementary dense implementation, each Boolean matrix multiplication evaluates all $n^3$ triples $(i,t,j)$, with no early exit. Each equality test costs $O(n^2)$. Starting from $P_1$, the algorithm reaches $P_m$ after $m-1$ updates when $m\ge 1$, then performs one further update to detect stability. Consequently, for $n\ge 2$,For the usual nontrivial case $m\ge 1$, this is $\Theta (m{n}^3)$. Since $m\le n-1$, the overall worst case is $\Theta (n^4)$. This bound is tight for this implementation: the directed chain $0\to 1\to \cdots \to n-1$ has $m=n-1$ and gains previously unknown pairs at every length until then, while every update scans all triples. This tightness does not claim an inherent lower bound for the reflexive transitive closure problem; it concerns the specified repeated-extension algorithm.

Split a graph path of length at most $2k$ into two consecutive parts of length at most $k$, allowing a zero-length part. Conversely, concatenating two such parts gives a walk of length at most $2k$ and hence the same reachability. ThereforeStart at $P_1=I\vee E$, then square to obtain $P_2,P_4,P_8,\dots$. Stop at equality of successive matrices, or after the length bound reaches $n-1$. The invariant is now $P=P_{2^r}$ after $r$ squarings. Equality implies closure under composition, and the included identity matrix ensures reflexivity.

For the same elementary dense Boolean matrix multiplication and equality stopping test, the cost isThe additive constant covers the final stability check and the cases $m=0,1$. Thus, with $m\ge 2$, the number of cubic passes falls from $\Theta (m)$ to $\Theta (\log m)$. In terms of $n$ alone the worst-case bound improves from $\Theta (n^4)$ to $\Theta (n^3\log n)$ for these implementations. A directed chain also requires logarithmically many squarings. This comparison uses ordinary triple-loop multiplication, rather than a faster matrix multiplication method.