GATE CS 1998 Q1.21 — Asymptotic Worst Case Time and Space Complexity

The standard algorithm for finding all-pairs shortest paths in a weighted graph is the Floyd-Warshall algorithm.

The Floyd-Warshall algorithm is a classic application of the Dynamic Programming design technique. It breaks the problem down into simpler subproblems and solves them bottom-up:

• Let $d_{ij}^{(k)}$ be the shortest path distance from vertex $i$ to vertex $j$ using only a subset of vertices from the set $\{1, 2, \dots, k\}$ as intermediate nodes.
• The recurrence relation used to compute the optimal solution is:
  $$d_{ij}^{(k)} = \min \left( d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)} \right)$$

Since it computes the shortest paths by reusing previously computed optimal subproblems, it utilizes dynamic programming.

Therefore, the correct option is A.