3.2k views

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?

1. Dynamic programming

2. Backtracking

3. Greedy

4. Divide and Conquer

edited | 3.2k views

Answer is $(A)$ because Floyd Warshall algorithm is used to find all shortest paths which is a dynamic programming approach.
edited
+3
@Arjun Sir plz tell why here we are not thinking about Dijkastra Algo.

Then greedy approach will be answer.
+8
Because that is a single source algorithm. In Cormen these are different headings.
+6

@srestha ji,

plz tell why here we are not thinking about Dijkastra Algo.

First of all good point. Dijkastra's Algo. could be used to find all pair shortest path( run it from each vartex) but it's time complexity will be more then Floyd Warshall Algorithm so option (C) is less appropriate.

+2

@Chhotu Time complexity of floyd algo is O(v^3), for dijkastra's algo is O(v^2) if we apply for all vertex it will be O(v^3). Why Floyd algo is preferred is

• Dijkastra's doesn't work for negative weight edges and we can avoid calculating the same thing over again in Floyd algo.
+1

smsubham  Dijkstra’s algo is O(E log V) and  Floyd algo is O(V3).And for finding all pair shortest paths by running Dijkstra for every vertex,this would be O(VE Log V) which can go (V3 Log V) in worst case. So its more than that of Floyd Warshall.

+1

@meghna , running time of Dijkstra's algo depends on which data structure we use to store information...

1) using Array data structure , running time $\in$ $O(|V|^{2})$

2) using Binary Heap data structure , running time $\in$ $O((|E|+|V|)(lg|V|))$

3) using Fibonacci Heap data structure , running time $\in$ $O(|E|+|V|(lg|V|))$

reshown by

1
2