G (V, E) be a directed graph with n vertices. A path from
G is sequence of vertices
(vi, vi+1, ……., vj) such that
(vk, vk+1) ∈ E for all
j – 1.
A simple path is a path in which no vertex appears more than once.
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)