GATE CSE 1998 | Question: 1.21, ISRO2008-16

Question

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

• A. Dynamic programming

• B. Backtracking

• C. Greedy

• D. Divide and Conquer

Answer 1

Answer is $(A)$ because Floyd Warshall algorithm is used to find all shortest paths which is a dynamic programming approach.

Comments

@ smsubham  Dijkstra’s algo is O(E log V) and  Floyd algo is O(V³).And for finding all pair shortest paths by running Dijkstra for every vertex,this would be O(VE Log V) which can go (V³ 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|))$ 

---

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. 

Answer 2

The algorithm is an example of dynamic programming.
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm