Which of the following algorithm design technique is used in finding all pairs…

The correct answer is Dynamic programming. The All-Pairs Shortest Path problem, typically solved using the Floyd-Warshall algorithm, relies fundamentally on dynamic programming principles.

This technique breaks down a complex problem into simpler subproblems and stores the results of these subproblems to avoid redundant computations.

In Floyd-Warshall, we iteratively improve the shortest path estimates between all pairs of vertices by considering each vertex as an intermediate point. At each step k, the algorithm determines if a path from i to j through vertex k is shorter than the previously known shortest path, updating the distance matrix accordingly. This optimal substructure and overlapping subproblems property are hallmarks of dynamic programming.

Backtracking is used for constraint satisfaction problems, not shortest paths. Greedy algorithms make locally optimal choices at each step but cannot guarantee a globally optimal solution for all-pairs shortest paths, especially with negative weights. Divide and Conquer splits a problem into independent subproblems, whereas the Floyd-Warshall algorithm builds solutions incrementally based on previous results.