Q70

Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1}) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in which no vertex appears more than once. Let $A$ be an $n \times n$ array initialized as follows:

$$A[j,k] = \begin{cases} 1 \text {, if } (j,k) \in E \\ 0 \text{, otherwise} \end{cases}$$

Consider the following algorithm: for i=1 to n for j=1 to n for k=1 to n A[j,k] = max(A[j,k], A[j,i] + A[i,k]); Which of the following statements is necessarily true for all $j$ and $k$ after termination of the above algorithm?