Floyd-Warshall — All-Pairs Shortest Paths

The DP

long[][] dist = new long[n][n];
// Initialize with edge weights, INF otherwise
for (int k = 0; k < n; k++)
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

Interpretation

dist[i][j] after k iterations = shortest path using only vertices 0..k as intermediate.

Path reconstruction

Track predecessor: if (dist[i][k] + dist[k][j] < dist[i][j]) next[i][j] = next[i][k].

Negative cycles

Check dist[i][i] < 0 for any i. Presence indicates negative cycle.