The Gateway to Computer Science Excellence
+19 votes

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

  1. Greedy paradigm.
  2. Divide-and-conquer paradigm.
  3. Dynamic Programming paradigm.
  4. Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.
in Algorithms by Boss (41.9k points)
edited by | 2.1k views

Hope it will help  

4 Answers

+29 votes
Best answer
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
+6 votes
by Active (2.3k points)
+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 :-

by Boss (11.7k points)
+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).

by (365 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,367 answers
105,265 users