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] \leq n

2)If A[j,j] \geq 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

Though it looks like Floyd-Warshall Algorithm, but it is not that algorithm. Because it uses max length of all edges. But the options of this question confusing me. Plz tell me , how to find best option here.