2.1k views

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

4. Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

edited | 2.1k views
+2

Hope it will help

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$
by Loyal (8.2k points)
edited
by Active (2.3k points)

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

by Boss (11.7k points)

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

by (365 points)