Multiple choice

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?

  1. A[j,k] $\le$ n
  2. If A[j,j] $\ge$ n - 1, then G has a Hamiltonian cycle

  3. If there exists a path from j to k, A[j,k] contains the longest path length from j to k

  4. If there exists a path from j to k, every simple path from j to k contains at most A[j,k} edges
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Keep practicing — related questions