What is the formula to compute the transitive closure of a graph?(a) tij(k) = tij(k-1) AND (tik(k-1) OR tkj(k-1))(b) tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1))(c) tij(k) = tij(k-1) AND (tik(k-1) AND tkj(k-1))(d) tij(k) = tij(k-1) OR (tik(k-1) OR tkj(k-1))The question was posed to me in unit test.This intriguing question comes from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II

What is the formula to compute the transitive closure of a graph?(a) t

1.	What is the formula to compute the transitive closure of a graph?(a) tij(k) = tij(k-1) AND (tik(k-1) OR tkj(k-1))(b) tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1))(c) tij(k) = tij(k-1) AND (tik(k-1) AND tkj(k-1))(d) tij(k) = tij(k-1) OR (tik(k-1) OR tkj(k-1))The question was posed to me in unit test.This intriguing question comes from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II
Answer» CORRECT answer is (b) TIJ(k) = tij(k-1) OR (TIK(k-1) AND tkj(k-1)) Explanation: TRANSITIVE closure of a graph can be computed by using Floyd Warshall algorithm. This method involves substitution of logical operations (logical OR and logical AND) for arithmetic operations min and + in Floyd Warshall Algorithm. Floyd Warshall Algorithm: dij(k)=min(dij(k-1), dik(k-1) + dkj(k-1)) Transitive closure: tij(k)= tij(k-1) OR (tik(k-1) AND tkj(k-1)).

Discussion

No Comment Found

Related InterviewSolutions

What is the formula to compute the transitive closure of a graph?(a) tij(k) = tij(k-1) AND (tik(k-1) OR tkj(k-1))(b) tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1))(c) tij(k) = tij(k-1) AND (tik(k-1) AND tkj(k-1))(d) tij(k) = tij(k-1) OR (tik(k-1) OR tkj(k-1))The question was posed to me in unit test.This intriguing question comes from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II
In the given graph, how many intermediate vertices are required to travel from node a to node e at a minimum cost?(a) 2(b) 0(c) 1(d) 3The question was asked in exam.I need to ask this question from Shortest Path in division Shortest Path of Data Structures & Algorithms II
In the given graph, what is the minimum cost to travel from vertex 1 to vertex 3?(a) 3(b) 2(c) 10(d) -3The question was asked during an online exam.My question is taken from Shortest Path in section Shortest Path of Data Structures & Algorithms II
The time taken to compute the transitive closure of a graph is Theta(n^2).(a) True(b) FalseI have been asked this question in final exam.Asked question is from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II
Using logical operator’s instead arithmetic operators saves time and space.(a) True(b) FalseI got this question in quiz.This key question is from Shortest Path topic in division Shortest Path of Data Structures & Algorithms II
What happens when the value of k is 0 in the Floyd Warshall Algorithm?(a) 1 intermediate vertex(b) 0 intermediate vertex(c) N intermediate vertices(d) N-1 intermediate verticesThis question was addressed to me during an online exam.My query is from Shortest Path topic in division Shortest Path of Data Structures & Algorithms II
Who proposed the modern formulation of Floyd-Warshall Algorithm as three nested loops?(a) Robert Floyd(b) Stephen Warshall(c) Bernard Roy(d) Peter IngermanThe question was asked during an internship interview.Query is from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II
Floyd- Warshall algorithm was proposed by ____________(a) Robert Floyd and Stephen Warshall(b) Stephen Floyd and Robert Warshall(c) Bernad Floyd and Robert Warshall(d) Robert Floyd and Bernad WarshallThe question was asked in semester exam.This question is from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II
What procedure is being followed in Floyd Warshall Algorithm?(a) Top down(b) Bottom up(c) Big bang(d) SandwichI had been asked this question in a job interview.This interesting question is from Shortest Path in section Shortest Path of Data Structures & Algorithms II
Floyd Warshall Algorithm can be used for finding _____________(a) Single source shortest path(b) Topological sort(c) Minimum spanning tree(d) Transitive closureThe question was posed to me in homework.My doubt stems from Shortest Path topic in chapter Shortest Path of Data Structures & Algorithms II

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment