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 (59.9k points)
edited by | 3.1k 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 Loyal (6k 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
47,913 questions
52,293 answers
67,739 users