|Que.||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]);
Which of the following statements is necessarily true for all j and k after terminal of the above algorithm ?
|a.||A[j, k] ≤ n|
|b.||If A[j, k] ≥ n - 1, then G has a Hamiltonian cycle|
|c.||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|
|Answer:If there exists a path from j to k, every simple path from j to k contain most A[j, k] edges|