Graph Algorithm 20

19Let 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

Forgot your password?

I agree with the Terms.