Project ForgeAlgorithms
Dynamic Programming & Greedy Algorithms
GATE 2016
Easy
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
- AGreedy paradigm
- BDivide-and-Conquer paradigm
- Dynamic Programming paradigm
- Dneither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm
Explanation
Floyd-Warshall builds up all-pairs shortest-path distances incrementally by considering each vertex as a potential intermediate point, reusing previously-computed shorter-path subproblems — the textbook definition of dynamic programming.
Source: GATE CS 2016 (Session 2 / Set B) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.