 # Gate 2003 Question on Graphs-Algorithm

#1

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)