Codex @codex  0

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.

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.