389. Floyd-Warshall - All-Pairs Shortest Paths

Given a directed weighted graph with n vertices (0-indexed) and m edges (each u, v, weight - weights may be negative, but there is no negative-weight cycle anywhere in the graph), find the shortest distance between every pair of vertices using the Floyd-Warshall algorithm. Print n lines, each with n space-separated distances (row i, column j = shortest distance from i to j); print 'INF' where no path exists, and 0 on the diagonal.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains three integers u v w, a directed weighted edge (weights may be negative, with no negative cycle). Output: Print n lines, each with n space-separated distances, where 'INF' marks unreachable pairs and the diagonal is 0.

1 <= n <= 500

Floyd-Warshall is specifically the right tool when you need ALL PAIRS' distances - for a SINGLE source's shortest paths, Dijkstra (non-negative weights) or Bellman-Ford (handles negative weights) alone is more efficient than running the full O(n³) all-pairs algorithm.

Find the shortest distance between every pair of vertices in a weighted graph, all at once. Brute force: Run Dijkstra's or Bellman-Ford's algorithm separately from EVERY single vertex as a source - this works (giving the same all-pairs result) but requires n separate runs, each with its own overhead, when Floyd-Warshall computes everything in one unified triple-loop. Optimised: The KEY insight is considering vertices as INTERMEDIATE stops one at a time (the outermost loop variable k) - after processing vertex k, the matrix correctly reflects the shortest paths that are allowed to use ONLY vertices 0 through k as intermediate stops, and by the time all n vertices have been considered as k, every possible intermediate combination has been accounted for.

First run a single Bellman-Ford pass from an added virtual source connected to all vertices with 0-weight edges, producing potentials h(v) used to reweight every edge to a non-negative value without changing which paths are shortest. With all edges now non-negative, run Dijkstra's algorithm (with a binary heap) from every vertex to get all-pairs shortest paths in O(n*m log n) total, then convert distances back using the potentials. This is faster than repeated Bellman-Ford on sparse graphs, but it is considerably more complex to implement correctly than a direct DP. Time: O(n*m log n + n*m) Space: O(n^2)

Initialize dist[i][j] as the direct edge weight (or infinity if none, 0 on the diagonal), then for each vertex k from 0 to n-1, update every pair dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) - meaning 'is it shorter to go from i to j via k'. After allowing every vertex in turn as an intermediate stop, dist[i][j] holds the true shortest distance for every pair. This handles negative edge weights directly (as long as there's no negative cycle) with a simple triple-nested loop and no auxiliary graph transformations, making it the simplest and most reliable choice for the given constraint n <= 500. Time: O(n^3) Space: O(n^2)

Run the Bellman-Ford algorithm independently starting from each of the n vertices. Bellman-Ford correctly handles negative edge weights (as long as there's no negative cycle) by relaxing all m edges up to n-1 times per source. Doing this once per source vertex gives the full all-pairs distance matrix, but repeating an O(n*m) algorithm n times costs O(n^2 * m) overall, which is noticeably slower than necessary when the graph is dense. Time: O(n^2 * m) Space: O(n^2)

1. Initialize an n x n distance matrix: 0 on the diagonal, direct edge weights where given, infinity everywhere else. 2. For every possible INTERMEDIATE vertex k (as the OUTERMOST loop), and every pair (i, j), check if routing i to j THROUGH k (dist[i][k] + dist[k][j]) beats the current dist[i][j] - update if so. 3. After considering every vertex as a possible intermediate stop, the matrix holds the true shortest distance between every pair.

Time: O(n³) - the triple nested loop over all (k, i, j) combinations. Space: O(n²), for the distance matrix.

Test n = 1 (a single line printing just 0), a graph with disconnected vertex pairs (printed as 'INF'), and n at the upper bound of 500 for the O(n^3) algorithm.

Be ready to explain WHY the loop order matters so critically (k must be the OUTERMOST loop) - processing i or j as the outer loop instead would break the algorithm's correctness, since it relies on k's paths being FULLY finalized before being used as an intermediate for other pairs.