Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?
Dynamic programming
Backtracking
Greedy
Divide and Conquer
@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
@ smsubham Dijkstra’s algo is O(E log V) and Floyd algo is O(V^{3}).And for finding all pair shortest paths by running Dijkstra for every vertex,this would be O(VE Log V) which can go (V^{3} Log V) in worst case. So its more than that of Floyd Warshall.
The algorithm is an example of dynamic programming. http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
Gatecse