The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
GATE CS - 2016,
Answer: C
Floyd-Warshall is based on the Dynamic Programming paradigm.
It computes \(d_{k}(i, j)\), the shortest path from \(i\) to \(j\) using only the first \(k\) vertices as intermediates, from the previous table:
\[ \begin{aligned} d_{k}(i,j) = \min(&d_{k-1}(i,j), \\ &d_{k-1}(i,k) + d_{k-1}(k,j)) \end{aligned} \]
This builds the solution from overlapping subproblems stored in a table, the defining feature of dynamic programming, and runs in \(O(n^{3})\).
It is not greedy: Dijkstra’s algorithm is the greedy shortest-path method, fixing one vertex at a time. It is not divide-and-conquer, which splits a problem into independent subproblems; the subproblems here overlap and are reused.
Please log in or register to report this question.