The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 votes

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

asked in Algorithms by Veteran (52k points)
edited by | 3.2k views

2 Answers

+19 votes
Best answer
Answer is $(A)$ because Floyd Warshall algorithm is used to find all shortest paths which is a dynamic programming approach.
answered by Junior (569 points)
edited by
@Arjun Sir plz tell why here we are not thinking about Dijkastra Algo.

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

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


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

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.


@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|))$ 

+8 votes
answered by Active (5k points)
reshown by

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
49,530 questions
54,139 answers
71,068 users