An all-pairs shortest-paths problem is efficiently solved using :

Answer: Floyd-Warshall algorithm

Why this algorithm is correct:

Floyd-Warshall is a dynamic programming algorithm that computes shortest paths between all pairs of vertices. It maintains a distance matrix and iteratively allows each vertex to act as an intermediate node, updating pairwise distances when a shorter path through that intermediate is found.

1. Initialize a distance matrix dist where dist[i][j] = weight(i,j) if an edge exists, dist[i][i] = 0, and dist[i][j] = ∞ otherwise.

2. For each vertex k from 1 to n, for each pair (i, j), set dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

3. After considering all k, dist[i][j] holds the shortest path distance from i to j.

Complexity and applicability:

• Time complexity: O(n^3). Space complexity: O(n^2).

• Handles negative edge weights correctly; if a negative cycle exists, it can be detected because some dist[i][i] becomes negative.

• Best used as a direct all-pairs algorithm, especially for dense graphs or when negative weights are present.

Why the other algorithms are not the best fit for all-pairs:

• Dijkstra's algorithm computes shortest paths from a single source and requires non-negative edge weights; repeating it for every source is possible but usually less efficient for dense graphs.

• Bellman-Ford also solves the single-source shortest-path problem and handles negative weights, but running it from every vertex is typically slower than Floyd-Warshall for all-pairs.

• Kruskal's algorithm finds a minimum spanning tree, which is a different problem and does not provide shortest paths between all pairs of vertices.