21 votes 21 votes The Floyd-Warshall algorithm for all-pair shortest paths computation is based on Greedy paradigm. Divide-and-conquer paradigm. Dynamic Programming paradigm. Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm. Algorithms gatecse-2016-set2 algorithms dynamic-programming easy + – Akash Kanase asked Feb 12, 2016 edited Jun 30, 2017 by Silpa Akash Kanase 7.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 33 votes 33 votes 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$ Anurag_s answered Feb 12, 2016 edited Apr 29, 2019 by Naveen Kumar 3 Anurag_s comment Share Follow See all 0 reply Please log in or register to add a comment.
6 votes 6 votes http://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/ viv696 answered Feb 12, 2016 viv696 comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes 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/ Rishi yadav answered Oct 20, 2017 Rishi yadav comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes 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). Nagamani answered Feb 6, 2018 Nagamani comment Share Follow See all 0 reply Please log in or register to add a comment.