GATE CS 2016 Set 2 Q.24 (CS Q.14): Dynamic Programming

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

Greedy paradigm.

Divide-and-Conquer paradigm.

Dynamic Programming paradigm.

neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

Official answer and solution

Official answer: C
From: Official GATE 2016 answer key

Solution

Recall the algorithmic paradigm used by the Floyd-Warshall all-pairs shortest paths algorithm.

The Floyd-Warshall algorithm computes all-pairs shortest paths for a directed graph with positive or negative edge weights (with no negative cycles).

It uses dynamic programming by defining subproblems based on the set of intermediate vertices allowed:
Let $d_{ij}^{(k)}$ be the shortest path from vertex $i$ to vertex $j$ using only intermediate vertices from the set $\{1, 2, \dots, k\}$ . The recurrence relation is:

d_{ij}^{(k)} = \min\left(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right)

Because it builds solutions to larger subproblems from optimal solutions to smaller subproblems with overlapping structure, it is a canonical example of the Dynamic Programming paradigm.

Hence, option (C) is correct.

Final answer

Common trap

Confusing Floyd-Warshall (Dynamic Programming) with Dijkstra's algorithm (Greedy).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 24 of 65, printed as CS Q.14
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source