## 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 ? |

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 |