GATE CSE 2016 Set 2 | Question: 14

Question

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

• A. Greedy paradigm.
• B. Divide-and-conquer paradigm.
• C. Dynamic Programming paradigm.
• D. Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

Answer 1

In Floyd Warshall's, we calculate all possibilities and select best one so its neither Divide & Conquer nor Greedy but based on Dynamic Programming Paradigm.

Correct Answer: $C$

Answer 2

http://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/

Answer 3

Floyd Warshall Algorithm is a Dynamic Programming based algorithm.

It finds all pairs shortest paths using following recursive nature of problem.

For every pair (i, j) of source and destination vertices respectively, there are two possible cases.
1) k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it is.
2) k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as dist[i][k] + dist[k][j].

Reference :-http://www.geeksforgeeks.org/gate-gate-cs-2016-set-2-question-24/

Answer 4

C)Dynamic programming paradigm. Because we compute all pair shortest path time complexity is O(V^3 log V) in case of dense graph  by using dijkstra algorithm and we use Bellman ford algorithm for this we get O(V^4) time complexity. By using dynamic programming method we get time complexity is less to compare other algorithms . Dynamic programming time complexity is O(n^3).