Gate 2003 Question on Graphs-Algorithm


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

enter image description here

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)