Floyd-Warshall
高级Floyd-Warshall 枚举中间节点，O(V³) 求出所有点对最短路。
// 算法讲解
Floyd-Warshall
输入节点数和带权边，观察 Floyd-Warshall 全源最短路计算。
待机
速度 中
待机 ⌨1void floyd(vector<vector<long long>>& dist) {
2 int n = dist.size();
3 for (int k = 0; k < n; k++)
4 for (int i = 0; i < n; i++)
5 for (int j = 0; j < n; j++)
6 if (dist[i][k] + dist[k][j] < dist[i][j])
7 dist[i][j] = dist[i][k] + dist[k][j];
8}
复杂度分析
时间 O(V³)
空间 O(V²)
最优 O(V³)
最坏 O(V³)
算法讲解
Floyd-Warshall 的核心是枚举中间节点 k，检查是否 dist[i][j] > dist[i][k] + dist[k][j]。
三重循环的顺序必须是 k → i → j，因为每个 k 代表"允许经过前 k 个节点"的最短路。
时间复杂度 O(V³)，空间复杂度 O(V²)，适用于稠密图或需要全源最短路的场景。
它还可以用来检测负环：如果最终 dist[i][i] < 0，说明存在负环。