Follow Us :

Graph Algorithm 20

0. Let G = (V, E) be a direction graph with n vertices. A path from vi to v in G is sequence of vertices (vi, 1, ..., such that (vk, vki)E 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 (AU, 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?

  • Option : D
  • Explanation :
    for i = 1 ton
    for j = 1 ton
    for K = 1 ton
    A[j, K] = max (j, K], A[j, i) + a(i, K)]
    Anxn Matrix and A[j, K] = 1 if (j, K) ∈ E
    so there exist a path from J to K and must contain A[j, K] edges
Cancel reply
Cancel reply