Floyd-Warshall
O(n³)All-pairs shortest paths in three nested loops over a distance matrix. Handles negative edges; a negative dist[i][i] afterward means i is on a negative cycle. The n ≤ 500 workhorse, and the base for transitive closure with booleans.
// use it on
CSES: Shortest Routes II ↗
Many distance queries on a small dense graph. Run once, answer each query from the matrix.
// the code
// dist = adjacency matrix: 0 on the diagonal, INF where no edge
// (use INF ~ LLONG_MAX / 4 so additions cannot overflow)
void floyd_warshall(vector<vector<long long>>& dist) {
int n = dist.size();
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
// negative cycle through i afterwards: dist[i][i] < 0// more shortest paths