Floyd-Warshall-Algorithm

Question 1

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

A
Greedy paradigm.
B
Divide-and-Conquer paradigm.
C
Dynamic Programming paradigm.
D
Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.
       Algorithms       Floyd-Warshall-Algorithm       GATE 2016 set-2
Question 1 Explanation: 
→ All Pair shortest path algorithm is using Dynamic Programming technique.
It takes worst case time complexity is O(|V|3) and worst case space complexity is O(|V|2).
→ The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
→ A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices.
Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.
There is 1 question to complete.
PHP Code Snippets Powered By : XYZScripts.com