Floyd-Warshall computes shortest paths between every pair of vertices in a weighted graph. It uses a 3-nested-loop DP: for each intermediate vertex k, update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). It runs in O(V³) and handles negative edges (but not negative cycles).
void floydWarshall(vector<vector<int>>& dist, int n) {
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];
}Unlike Dijkstra (single source), Floyd-Warshall computes shortest paths between every pair of vertices. The result is an n×n matrix where dist[i][j] is the shortest path from i to j.
dist[i][j][k] = shortest path from i to j using only vertices 0..k as intermediates. The recurrence is dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1]). This simplifies to an in-place 2D array.
After running Floyd-Warshall, if any dist[i][i] < 0, there is a negative cycle reachable from i. The algorithm cannot produce correct results when negative cycles exist.
Quiz coming soon for this algorithm.