The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to ___________(a) Total number of vertices(b) Total number of edges(c) Number of vertices – 1(d) Number of edges – 1This question was addressed to me at a job interview.This is a very interesting question from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II

The maximum number of times the decrease key operation performed in Di

1.	The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to ___________(a) Total number of vertices(b) Total number of edges(c) Number of vertices – 1(d) Number of edges – 1This question was addressed to me at a job interview.This is a very interesting question from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II
Answer» CORRECT CHOICE is (b) Total number of edges Easiest explanation - If the total number of edges in all adjacency list is E, then there will be a total of E number of ITERATIONS, hence there will be a total of at most E DECREASE key OPERATIONS.

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