edited by
7,203 views

4 Answers

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$
edited by
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/

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

Answer:

Related questions

15 votes
15 votes
4 answers
3
27 votes
27 votes
5 answers
4
Akash Kanase asked Feb 12, 2016
9,330 views
Anarkali digitally signs a message and sends it to Salim. Verification of the signature by Salim requires.Anarkali's public key.Salim's public key.Salim's private key.Ana...