Discussion
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
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.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development