= Solution
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>. Therefore
$$
\boxed{P_{k+1}[i,j]=P_k[i,j]\lor\bigvee_{t=0}^{n-1}\bigl(P_k[i,t]\land E[t,j]\bigr).}
$$
The 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\lor(P_k\odot E)$. Because $P_1$ includes the <identity matrix>, an equivalent formula is
$$
\boxed{P_{k+1}=P_k\odot P_1.}
$$
Compute each new <matrix> from an unchanged copy of the preceding <matrix>, so the subscript continues to specify exactly the length bound.
Back to article page
