25 votes 25 votes 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 Algorithms gate1998 algorithms algorithm-design-technique easy isro2008 + – Kathleen asked Sep 25, 2014 • edited Dec 4, 2022 by Lakshman Bhaiya Kathleen 9.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 27 votes 27 votes Answer is $(A)$ because Floyd Warshall algorithm is used to find all shortest paths which is a dynamic programming approach. sshekhar94 answered Mar 7, 2016 • edited Jun 24, 2018 by Shikha Mallick sshekhar94 comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments meghna commented Jul 14, 2018 reply Follow Share @ 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. 4 votes 4 votes ankitgupta.1729 commented Oct 6, 2018 reply Follow Share @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|))$ 15 votes 15 votes Abhrajyoti00 commented Dec 8, 2022 reply Follow Share Giving an insight to @ankitgupta.1729 Sir’s answer from algorithm - The Big O on the Dijkstra Fibonacci-heap solution - Stack Overflow The complexity of Dijkstra's shortest path algorithm is: O(|E| |decrease-key(Q)| + |V| |extract-min(Q)|) For both a Fibonacci heap and a binary heap, the complexity of the extract-min operation on this queue is O(log |V|). This explains the common |V| log |V| part in the sum. In the remaining part of the sum (the one with the edge factor |E|), the O(1) v.s. O(log |V|) difference comes precisely from using respectively a Fibonacci heap as opposed to a binary heap. The decrease key operation which may happen for every edge has exactly this complexity. So the remaining part of the sum eventually has complexity O(|E|) for a Fibonacci heap and O(|E| log |V|) for a binary heap. 1 votes 1 votes Please log in or register to add a comment.
9 votes 9 votes The algorithm is an example of dynamic programming.http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm Mithlesh Upadhyay answered Mar 17, 2015 • reshown Nov 6, 2016 by srestha Mithlesh Upadhyay comment Share Follow See all 0 reply Please log in or register to add a comment.