← All problems
#73 All Pairs Shortest Paths Hard

Given a weighted directed graph of N vertices represented as an N × N distance matrix, compute the shortest path distance between every pair of vertices using the Floyd-Warshall algorithm. The matrix is stored as a flat array in row-major order: dist[i * N + j] is the weight of the directed edge from vertex i to vertex j. A value of +infinity means no direct edge exists. The diagonal is always zero. For each intermediate vertex k from 0 to N - 1 (in order), update all pairs:

\[ \text{output}[i][j] = \min\!\bigl(\text{output}[i][j],\; \text{output}[i][k] + \text{output}[k][j]\bigr) \quad \forall\, i, j \]

Implementation Requirements

Example:

Input: N = 4
dist = [
  0,   5, inf,  10,   // row 0: edges from vertex 0
  inf, 0,   3, inf,   // row 1: edges from vertex 1
  inf, inf, 0,   1,   // row 2: edges from vertex 2
  inf, inf, inf, 0    // row 3: edges from vertex 3
]

Output:
output = [
  0,   5,   8,   9,   // shortest paths from vertex 0
  inf, 0,   3,   4,   // shortest paths from vertex 1
  inf, inf, 0,   1,   // shortest paths from vertex 2
  inf, inf, inf, 0    // shortest paths from vertex 3
]

Explanation:
- output[0][2] = 8   (path 0 -> 1 -> 2, cost 5 + 3 = 8)
- output[0][3] = 9   (path 0 -> 1 -> 2 -> 3, cost 5 + 3 + 1 = 9, beats direct 0 -> 3 = 10)
- output[1][3] = 4   (path 1 -> 2 -> 3, cost 3 + 1 = 4)

Constraints

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.