A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

Discussion Forum

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 ?
directed graph
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
Confused About the Answer? Ask for Details Here
Know Explanation? Add it Here

Similar Questions: