Let `G (V, E)`

be a directed graph with n vertices. A path from `vi`

to `vj`

in `G`

is sequence of vertices `(vi, vi+1, ……., vj)`

such that `(vk, vk+1) ∈ 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 x n`

array initialized as follow

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]);
```

I am not able to begin how to solve this.Please kindly help.

In question it’s been asked that which one is the correct option -

(A) A[j, k] ≤ n

(B) If A[j, k] ≥ n – 1, then G has a Hamiltonian cycle.

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

path lens from j to k.(D) If there exists a path from j to k, every simple path from j to k

contain most A[j, k] edges

I understand, folks here don’t solve questions, but this question came in an entrance exam for doing Masters in CS and I’m unable to think of a way from where to begin and if someone just give me a Graph to consider and some pointers that’d be really awesome.

P.S - Correct answer is option (d)