32 + Interview Questions in Shortest Path in Data Structures & Algorithms Ii Page 1 InterviewSolution

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

2.	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
Answer» Right choice is (C) 1 Explanation: The MINIMUM cost to TRAVEL from node a to node e is 1 by passing VIA nodes B and c. a-b, cost 5 b-c, cost 3 c-e, cost -7 Hence the total cost is 1.

Discussion

3.	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
Answer» Correct choice is (d) -3 The EXPLANATION is: The minimum cost required to travel from node 1 to node 5 is -3. 1-5, cost is -4 5-4, cost is 6 4-3, cost is -5 Hence total cost is -4 + 6 + -5 = -3.

Discussion

4.	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
Answer» Right choice is (B) False Explanation: The time taken to compute the transitive CLOSURE of a GRAPH is THETA(n^3). Transitive closure can be computed by assigning weight of 1 to each edge and by running Floyd Warshall Algorithm.

Discussion

5.	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
Answer» The correct choice is (a) True The best I can explain: In computers, logical OPERATIONS on single bit VALUES execute FASTER than arithmetic operations on INTEGER words of DATA.

Discussion

6.	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
Answer» RIGHT CHOICE is (b) 0 intermediate vertex Easiest explanation - When k=0, a path from vertex i to vertex j has no intermediate vertices at all. Such a path has at most one edge and HENCE dij(0) = wij.

Discussion

7.	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
Answer» RIGHT option is (d) PETER Ingerman The best I can explain: The modern formulation of Floyd-Warshall Algorithm as three NESTED for-loops was proposed by Peter Ingerman in the YEAR 1962.

Discussion

8.	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
Answer» The CORRECT answer is (a) Robert Floyd and Stephen Warshall The BEST I can explain: Floyd- Warshall Algorithm was proposed by Robert Floyd in the year 1962. The same algorithm was proposed by Stephen Warshall during the same year for FINDING the TRANSITIVE CLOSURE of the graph.

Discussion

9.	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
Answer» Right answer is (B) Bottom up Best explanation: Bottom up procedure is being used to compute the values of the matrix elements dij(k). The INPUT is an N X n matrix. The procedure returns the matrix D(n) of the SHORTEST path weights.

Discussion

10.	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
Answer» Correct answer is (d) Transitive closure The best explanation: One of the ways to compute the transitive closure of a graph in THETA(N^3) time is to assign a weight of 1 to each edge of E and then run the Floyd WARSHALL Algorithm.

Discussion

11.	What approach is being followed in Floyd Warshall Algorithm?(a) Greedy technique(b) Dynamic Programming(c) Linear Programming(d) BacktrackingI got this question in semester exam.I want to ask this question from Shortest Path in portion Shortest Path of Data Structures & Algorithms II
Answer» The CORRECT answer is (b) DYNAMIC Programming The best I can explain: Floyd Warshall ALGORITHM FOLLOWS dynamic programming approach because the all pair shortest paths are computed in bottom up manner.

Discussion

12.	What is the running time of the Floyd Warshall Algorithm?(a) Big-oh(V)(b) Theta(V^2)(c) Big-Oh(VE)(d) Theta(V^3)I got this question during an interview.I want to ask this question from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II
Answer» Right ANSWER is (d) Theta(V^3) Explanation: The running TIME of the Floyd Warshall algorithm is determined by the TRIPLY nested for LOOPS. Since each execution of the for LOOP takes O(1) time, the algorithm runs in time Theta(V^3).

Discussion

13.	Floyd Warshall’s Algorithm can be applied on __________(a) Undirected and unweighted graphs(b) Undirected graphs(c) Directed graphs(d) Acyclic graphsThis question was posed to me in an online interview.This intriguing question comes from Shortest Path topic in division Shortest Path of Data Structures & Algorithms II
Answer» Right CHOICE is (c) Directed graphs Best explanation: Floyd Warshall Algorithm can be APPLIED in directed graphs. From a given directed graph, an ADJACENCY MATRIX is FRAMED and then all pair shortest path is computed by the Floyd Warshall Algorithm.

Discussion

14.	Floyd Warshall’s Algorithm is used for solving ____________(a) All pair shortest path problems(b) Single Source shortest path problems(c) Network flow problems(d) Sorting problemsI got this question in exam.This intriguing question originated from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II
Answer» RIGHT answer is (a) All pair shortest path PROBLEMS The explanation is: Floyd WARSHALL’s ALGORITHM is used for solving all pair shortest path problems. It means the algorithm is used for finding the shortest PATHS between all pairs of vertices in a graph.

Discussion

15.	A graph is said to have a negative weight cycle when?(a) The graph has 1 negative weighted edge(b) The graph has a cycle(c) The total weight of the graph is negative(d) The graph has 1 or more negative weighted edgesI had been asked this question during an interview.This is a very interesting question from Shortest Path topic in chapter Shortest Path of Data Structures & Algorithms II
Answer» The correct ANSWER is (c) The total WEIGHT of the graph is negative For explanation: When the total weight of the graph sums up to a negative NUMBER then the graph is SAID to have a negative weight cycle. Bellmann Ford Algorithm provides no solution for such GRAPHS.

Discussion

16.	Bellmann Ford Algorithm is an example for ____________(a) Dynamic Programming(b) Greedy Algorithms(c) Linear Programming(d) Branch and BoundI have been asked this question in final exam.My question is taken from Shortest Path in chapter Shortest Path of Data Structures & Algorithms II
Answer» CORRECT OPTION is (a) Dynamic Programming For EXPLANATION: In Bellmann Ford Algorithm the SHORTEST paths are calculated in bottom up manner which is similar to other dynamic programming problems.

Discussion

17.	In the given graph, identify the path that has minimum cost to travel from node a to node f.(a) a-b-c-f(b) a-d-e-f(c) a-d-b-c-f(d) a-d-b-c-e-fThe question was posed to me in exam.This intriguing question comes from Shortest Path in portion Shortest Path of Data Structures & Algorithms II
Answer» The CORRECT choice is (d) a-d-b-c-e-f Easy explanation - The minimum COST taken by the path a-d-b-c-e-f is 4. a-d, cost=2 d-b, cost=-2 b-c, cost=1 c-e, cost= 2 e-f, cost=1 Hence the TOTAL cost is 4.

Discussion

18.	Consider the following graph. What is the minimum cost to travel from node A to node C?(a) 5(b) 2(c) 1(d) 3The question was posed to me in an online quiz.Question is from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II
Answer» The correct choice is (b) 2 Easy explanation - The MINIMUM COST to TRAVEL from node A to node C is 2. A-D, cost=1 D-B, cost=-2 B-C, cost=3 Hence the total cost is 2.

Discussion

19.	Bellmann Ford algorithm was first proposed by ________(a) Richard Bellmann(b) Alfonso Shimbe(c) Lester Ford Jr(d) Edward F. MooreI got this question in an interview for internship.This interesting question is from Shortest Path topic in chapter Shortest Path of Data Structures & Algorithms II
Answer» Right answer is (b) ALFONSO Shimbe For EXPLANATION: Alfonso Shimbe proposed Bellmann FORD ALGORITHM in the year 1955. Later it was published by Richard Bellmann in 1957 and Lester Ford Jr in the year 1956. Hence it is called Bellmann Ford Algorithm.

Discussion

20.	Bellmann Ford Algorithm can be applied for _____________(a) Undirected and weighted graphs(b) Undirected and unweighted graphs(c) Directed and weighted graphs(d) All directed graphsI got this question in an interview for job.I need to ask this question from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II
Answer» Right choice is (c) Directed and weighted graphs Easy explanation - Bellmann Ford ALGORITHM can be applied for all directed and weighted graphs. The WEIGHT function in the GRAPH may EITHER be positive or negative.

Discussion

21.	How many solution/solutions are available for a graph having negative weight cycle?(a) One solution(b) Two solutions(c) No solution(d) Infinite solutionsI have been asked this question during an online exam.My doubt stems from Shortest Path in division Shortest Path of Data Structures & Algorithms II
Answer» RIGHT option is (c) No solution The BEST EXPLANATION: If the graph has any negative weight cycle then the algorithm indicates that no solution EXISTS for that graph.

Discussion

22.	Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not.(a) True(b) FalseI had been asked this question in an online interview.My question comes from Shortest Path topic in division Shortest Path of Data Structures & Algorithms II
Answer» RIGHT answer is (a) True Easiest explanation - Bellmann Ford algorithm returns true if the GRAPH does not have any NEGATIVE WEIGHT cycles and returns false when the graph has negative weight cycles.

Discussion

23.	Bellmann ford algorithm provides solution for ____________ problems.(a) All pair shortest path(b) Sorting(c) Network flow(d) Single source shortest pathI had been asked this question in an online quiz.Query is from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II
Answer» Correct OPTION is (d) Single SOURCE shortest path The best I can EXPLAIN: Bellmann ford ALGORITHM is used for finding solutions for single source shortest path problems. If the graph has no negative cycles that are reachable from the source then the algorithm PRODUCES the shortest paths and their weights.

Discussion

24.	The Bellmann Ford algorithm returns _______ value.(a) Boolean(b) Integer(c) String(d) DoubleThe question was asked in an interview.My question is taken from Shortest Path topic in division Shortest Path of Data Structures & Algorithms II
Answer» The correct CHOICE is (a) Boolean To explain: The Bellmann Ford algorithm returns Boolean VALUE whether there is a negative weight CYCLE that is reachable from the SOURCE.

Discussion

25.	Dijkstra’s Algorithm is the prime example for ___________(a) Greedy algorithm(b) Branch and bound(c) Back tracking(d) Dynamic programmingI have been asked this question in an international level competition.My question is from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II
Answer» Right answer is (a) Greedy algorithm Explanation: DIJKSTRA’s Algorithm is the prime EXAMPLE for greedy algorithms because greedy algorithms GENERALLY solve a problem in stages by doing what appears to be the best THING at each STAGE.

Discussion

26.	In the given graph, identify the shortest path having minimum cost to reach vertex E if A is the source vertex.(a) a-b-e(b) a-c-e(c) a-c-d-e(d) a-c-d-b-eThe question was posed to me during an internship interview.I'm obligated to ask this question of Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II
Answer» Correct ANSWER is (b) a-C-e For explanation: The minimum cost REQUIRED to travel from vertex A to E is via vertex C A to C, cost= 3 C to E, cost= 2 Hence the total cost is 5.

Discussion

27.	Dijkstra’s Algorithm run on a weighted, directed graph G={V,E} with non-negative weight function w and source s, terminates with d[u]=delta(s,u) for all vertices u in V.(a) True(b) FalseThe question was posed to me by my school principal while I was bunking the class.My question is taken from Shortest Path topic in division Shortest Path of Data Structures & Algorithms II
Answer» Correct answer is (a) True Best explanation: The equality d[U]=delta(s,u) holds good when vertex u is ADDED to set S and this equality is MAINTAINED THEREAFTER by the upper bound PROPERTY.

Discussion

28.	The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm.(a) True(b) FalseI have been asked this question in an interview for internship.I'd like to ask this question from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II
Answer» The correct choice is (B) False The explanation is: The NUMBER of iterations INVOLVED in Bellmann FORD Algorithm is more than that of Dijkstra’s Algorithm.

Discussion

29.	What is running time of Dijkstra’s algorithm using Binary min- heap method?(a) O(V)(b) O(VlogV)(c) O(E)(d) O(ElogV)The question was posed to me during an internship interview.My question is taken from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II
Answer» Correct choice is (d) O(ElogV) Explanation: Time required to build a binary MIN heap is O(V). Each decrease key operation TAKES O(logV) and there are still at most E such OPERATIONS. Hence TOTAL running time is O(ElogV).

Discussion

30.	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

31.	How many times the insert and extract min operations are invoked per vertex?(a) 1(b) 2(c) 3(d) 0The question was posed to me at a job interview.Question is from Shortest Path topic in division Shortest Path of Data Structures & Algorithms II
Answer» The correct choice is (a) 1 Easiest explanation - Insert and extract min operations are invoked only once per VERTEX because each vertex is added only once to the SET and each edge in the adjacency list is EXAMINED only once during the COURSE of algorithm.

Discussion

32.	Dijkstra’s Algorithm is used to solve _____________ problems.(a) All pair shortest path(b) Single source shortest path(c) Network flow(d) SortingThis question was posed to me in an online quiz.My question is from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II
Answer» Correct choice is (B) Single source shortest path Easiest explanation - Dijkstra’s Algorithm is used for solving single source shortest path PROBLEMS. In this algorithm, a single node is FIXED as a source node and shortest PATHS from this node to all other nodes in graph is found.

Discussion

Explore topic-wise InterviewSolutions in .

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

What approach is being followed in Floyd Warshall Algorithm?(a) Greedy technique(b) Dynamic Programming(c) Linear Programming(d) BacktrackingI got this question in semester exam.I want to ask this question from Shortest Path in portion Shortest Path of Data Structures & Algorithms II

What is the running time of the Floyd Warshall Algorithm?(a) Big-oh(V)(b) Theta(V^2)(c) Big-Oh(VE)(d) Theta(V^3)I got this question during an interview.I want to ask this question from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II

Bellmann Ford Algorithm is an example for ____________(a) Dynamic Programming(b) Greedy Algorithms(c) Linear Programming(d) Branch and BoundI have been asked this question in final exam.My question is taken from Shortest Path in chapter Shortest Path of Data Structures & Algorithms II

In the given graph, identify the path that has minimum cost to travel from node a to node f.(a) a-b-c-f(b) a-d-e-f(c) a-d-b-c-f(d) a-d-b-c-e-fThe question was posed to me in exam.This intriguing question comes from Shortest Path in portion Shortest Path of Data Structures & Algorithms II

Consider the following graph. What is the minimum cost to travel from node A to node C?(a) 5(b) 2(c) 1(d) 3The question was posed to me in an online quiz.Question is from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II

Bellmann Ford algorithm was first proposed by ________(a) Richard Bellmann(b) Alfonso Shimbe(c) Lester Ford Jr(d) Edward F. MooreI got this question in an interview for internship.This interesting question is from Shortest Path topic in chapter Shortest Path of Data Structures & Algorithms II

Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not.(a) True(b) FalseI had been asked this question in an online interview.My question comes from Shortest Path topic in division Shortest Path of Data Structures & Algorithms II

Bellmann ford algorithm provides solution for ____________ problems.(a) All pair shortest path(b) Sorting(c) Network flow(d) Single source shortest pathI had been asked this question in an online quiz.Query is from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II

The Bellmann Ford algorithm returns _______ value.(a) Boolean(b) Integer(c) String(d) DoubleThe question was asked in an interview.My question is taken from Shortest Path topic in division Shortest Path of Data Structures & Algorithms II

The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm.(a) True(b) FalseI have been asked this question in an interview for internship.I'd like to ask this question from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II

What is running time of Dijkstra’s algorithm using Binary min- heap method?(a) O(V)(b) O(VlogV)(c) O(E)(d) O(ElogV)The question was posed to me during an internship interview.My question is taken from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II

How many times the insert and extract min operations are invoked per vertex?(a) 1(b) 2(c) 3(d) 0The question was posed to me at a job interview.Question is from Shortest Path topic in division Shortest Path of Data Structures & Algorithms II

Dijkstra’s Algorithm is used to solve _____________ problems.(a) All pair shortest path(b) Single source shortest path(c) Network flow(d) SortingThis question was posed to me in an online quiz.My question is from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II