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

Answer: Dynamic Programming paradigm.

Why:

• The algorithm defines d_k(i,j) as the shortest-path distance from vertex i to vertex j using only intermediate vertices from the set {1, …, k}.

• It uses the recurrence d_k(i,j) = min(d_{k-1}(i,j), d_{k-1}(i,k) + d_{k-1}(k,j)), which clearly builds each solution from earlier computed subsolutions.

• Because it solves overlapping subproblems and combines them according to a recurrence, this is dynamic programming.

Implementation (conceptual pseudocode):

1. Initialize dist[i][j] = weight(i,j) if edge exists, 0 if i = j, otherwise +infinity.

2. For k from 1 to n:

3. For i from 1 to n:

4. For j from 1 to n:

5. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

• Time complexity: O(n^3) due to the three nested loops.

• Works with negative edge weights but will not produce meaningful shortest paths if a negative-weight cycle exists; a negative cycle is detectable if dist[i][i] becomes negative for some i.