GATE CS 2016 Set 2 Q14 — Algorithm Design: Dynamic Programming

The Floyd-Warshall algorithm is a classic Dynamic Programming algorithm used to find the shortest paths between all pairs of vertices in a weighted graph (which may contain negative edge weights, but no negative cycles).

Reasoning:

• The algorithm breaks the problem down into overlapping subproblems.
• Let $d_{ij}^{(k)}$ represent the shortest path weight from vertex $i$ to vertex $j$ using only vertices from the set $\{1, 2, \dots, k\}$ as intermediate nodes.
• The optimal substructure is defined by the recurrence relation: $$d_{ij}^{(k)} = \min\left(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right)$$
• By computing and storing the solutions to these subproblems in a bottom-up manner (from $k = 0$ to $n$), it avoids redundant computations, which is the defining characteristic of the Dynamic Programming paradigm.

Therefore, the correct option is C.