青少年编程知识记录 codecoming

【图论】弗洛伊德算法（Floyd）

一、算法说明

Floyd 算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与 Dijkstra 算法类似。 该算法名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

Floyd 算法是解决多源最短路径问题的经典动态规划算法，它能在 O(n^3) 时间复杂度内求出图中所有节点对之间的最短路径，支持有向和无向图，支持权值为负数的情况（负权边），但不支持负权环（若图中存在负权环，环上节点的最短路径无意义）。





二、核心思想



Floyd 算法的核心是动态规划，通过引入 “中间节点” 的概念逐步松弛路径：定义 dp[k][i][j] 表示 “从节点 i 到节点 j，且仅允许经过编号为 1~k 的节点作为中间节点时的最短路径长度”。



1.邻接矩阵(二维数组)dist 储存路径，数组中的值开始表示点点之间初始直接路径，最终是点点之间的最小路径，有两点需要注意的， 第一是如果没有直接相连的两点那么默认为一个很大的值(不要因为计算溢出成负数)，第二是自己和自己的距离要为 0。

2 .从第 1 个到第 n 个点依次加入松弛计算，每个点加入进行试探枚举是否有路径长度被更改(自己能否更新路径)。顺序加入(k 枚举)松 弛的点时候，需要遍历图中每一个点对(i,j 双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化，如果发生改变(变 小)，那么两点(i,j)距离就更改。

3 .重复上述直到最后插点试探完成。 其中第 2 步的状态转移方程为: 

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])

其中 dp[a][b]的意思可以理解为点 a 到点 b 的最短路径,所以 dp[i][k]的意思可以理解为 i 到 k 的最短路径 dp[k][j]的意思为 k 到 j 的最短 路径. 





三、算法步骤



  1. 1.初始化：

    • 若 i == j，dp[i][j] = 0（自身到自身距离为 0）；

    • 若 i 和 j 之间有直接边，dp[i][j] = 边权；

    • 若 i 和 j 之间无直接边，dp[i][j] = 无穷大（如 0x3f3f3f3f）。

    • 构建邻接矩阵 dist，其中 dp[i][j] 表示节点 i 到 j 的初始距离：

  2. 2.状态转移：

    遍历所有可能的中间节点 k（1~n），再遍历所有起点 i 和终点 j，执行松弛操作：

    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);



  1. 3.结果输出：

    最终 dist[i][j] 即为 i 到 j 的最短路径长度；若仍为无穷大，说明 i 无法到达 j。

四、过程图解



我们使用以下有向图（顶点数为 4）：



顶点: 0, 1, 2, 3  边与权值:  0 ->1: 3  0 ->2： 6  1 ->2：-2  2 ->3： 2  3 ->0： 1

注意：图中存在负权边（1->2: -2 )









初始矩阵D(0)





0123
0036INF
1INF0-2INF
2INFINF02
31INFINF0

k = 0（允许经过顶点 0 作为中间点）

更新规则：对于所有 i, j，检查 D[i][0] + D[0][j] 是否小于 D[i][j]。

  • i=1, j=2: D[1][0]=INF, 不加。

  • i=3, j=1: D[3][0]=1, D[0][1]=3, 和=4，原来 D[3][1]=INF → 更新为 4。

  • i=3, j=2: D[3][0]=1, D[0][2]=6, 和=7，原来 INF → 更新为 7。

  • 其他无更新。



结果D(1)



0123
0036INF
1INF0-2INF
2INFINF02
31470

k = 1（允许经过顶点 0,1 作为中间点）

  • i=0, j=2: D[0][1]=3, D[1][2]=-2, 和=1，原来 D[0][2]=6 → 更新为 1。

  • i=0, j=3: D[0][1]=3, D[1][3]=INF → 无更新。

  • i=2, j=0: D[2][1]=INF → 无。

  • i=3, j=2: D[3][1]=4, D[1][2]=-2, 和=2，原来 D[3][2]=7 → 更新为 2。

  • i=3, j=0: D[3][1]=4, D[1][0]=INF → 无。



结果D(2)



0123
0031INF
1INF0-2INF
2INFINF02
31420

k = 2（允许经过顶点 0,1,2 作为中间点）

  • i=0, j=3: D[0][2]=1, D[2][3]=2, 和=3，原来 INF → 更新为 3。

  • i=1, j=3: D[1][2]=-2, D[2][3]=2, 和=0，原来 INF → 更新为 0。

  • i=1, j=0: D[1][2]=-2, D[2][0]=INF → 无。

  • i=3, j=0: D[3][2]=2, D[2][0]=INF → 无。

  • i=3, j=1: D[3][2]=2, D[2][1]=INF → 无。



结果D(3)



0123
00313
1INF0-20
2INFINF02
31420

k = 3（允许经过所有顶点作为中间点）

  • i=0, j=0: D[0][3]=3, D[3][0]=1, 和=4 > 0，不更新。

  • i=0, j=1: D[0][3]=3, D[3][1]=4, 和=7 > 3，不更新。

  • i=0, j=2: D[0][3]=3, D[3][2]=2, 和=5 > 1，不更新。

  • i=1, j=0: D[1][3]=0, D[3][0]=1, 和=1，原来 INF → 更新为 1。

  • i=1, j=1: 无意义。

  • i=1, j=2: D[1][3]=0, D[3][2]=2, 和=2 > -2，不更新。

  • i=2, j=0: D[2][3]=2, D[3][0]=1, 和=3，原来 INF → 更新为 3。

  • i=2, j=1: D[2][3]=2, D[3][1]=4, 和=6，原来 INF → 更新为 6。

  • i=3, j=0: 已是最优。

  • i=3, j=1: 已是最优。

  • i=3, j=2: 已是最优。



D(4)



0123
00313
110-20
23602
31420

4. 结果解释

最终矩阵给出了所有点对的最短路径长度：

  • 0 → 2 最短路径是 0→1→2，长度 3 + (-2) = 1。

  • 1 → 0 最短路径是 1→3→0，长度 0 + 1 = 1。

  • 2 → 1 最短路径是 2→3→0→1，长度 2 + 1 + 3 = 6。

  • 图中包含负权边（1→2 权重 -2），但没有负权回路，因此所有最短路径都有确定值。





五、参考代码



1.基本版本

#include <iostream>  #include <climits>  using namespace std;  const int MAXN = 100;  // 最大节点数  const int INF = 1e9;  // 表示无穷大  // Floyd算法  void floyd(int n, int dist[MAXN][MAXN]) {      // Floyd算法核心      for (int k = 0; k < n; k++) {          for (int i = 0; i < n; i++) {              if (dist[i][k] == INF) continue;  // 跳过无效路径              for (int j = 0; j < n; j++) {                  if (dist[k][j] == INF) continue;  // 跳过无效路径                  if (dist[i][j] > dist[i][k] + dist[k][j]) {                      dist[i][j] = dist[i][k] + dist[k][j];                  }              }          }      }  }    // 示例使用  int main() {      int n,m,w;  // 节点数,边，权重       int dist[MAXN][MAXN];      n=4;//假设4个顶点       // 初始化距离矩阵      for (int i = 0; i < n; i++) {          for (int j = 0; j < n; j++) {              if (i == j) {                  dist[i][j] = 0;              } else {                  dist[i][j] = INF;              }          }      }            // 添加边（测试输入）       dist[0][1] = 3;      dist[0][2] = 6;      dist[1][2] = -2;      dist[2][3] = 2;      dist[3][0] = 1;        //     题目输入   //     for (int i = 0; i < m; ++i) {  //        int u, v;  //        int w;  //        cin >> u >> v >> w;  //        dist[u][v] = min(dist[u][v], w);   //		//有向边；无向边需加 dist[v][u] = min(dist[v][u], w)  //    }            // 运行Floyd算法      floyd(n, dist);            // 输出结果      cout << "最短路径：" <<endl;          for (int i = 0; i < n; ++i) {          for (int j = 0; j < n; ++j) {              cout << i << "→" << j << "：";              if (dist[i][j] == INF) cout << "INF"<<endl;              else cout << dist[i][j] <<endl ;          }          cout << endl;      }      return 0;  }



2.带路径的

在上一个版本的基础上增加前驱矩阵，支持还原任意节点对的最短路径

#include <iostream>  #include <climits>  using namespace std;   const int MAXN = 100;  const int INF = 1e9;    // Floyd算法  void floyd(int n, int dist[MAXN][MAXN], int path[MAXN][MAXN]) {      // 初始化路径矩阵      for (int i = 0; i < n; i++) {          for (int j = 0; j < n; j++) {              if (i == j || dist[i][j] == INF) {                  path[i][j] = -1;  //不能走               } else {                  path[i][j] = i;  // 初始时，i到j的直接前驱是i              }          }      }            // Floyd算法核心      for (int k = 0; k < n; k++) {          for (int i = 0; i < n; i++) {              if (dist[i][k] == INF) continue;              for (int j = 0; j < n; j++) {                  if (dist[k][j] == INF) continue;                  if (dist[i][j] > dist[i][k] + dist[k][j]) {                      dist[i][j] = dist[i][k] + dist[k][j];                      path[i][j] = path[k][j];  // 更新路径                  }              }          }      }  }    // 递归打印路径  void print_path(int i, int j, int path[MAXN][MAXN]) {      if (path[i][j] == -1) {          cout << "无路径";          return;      }            if (i == j) {          cout << i;      } else if (path[i][j] == i) {           cout << i << " -> " << j;      } else {          print_path(i, path[i][j], path);          cout << " -> " << j;      }  }    // 示例使用  int main() {      int n,m,w; //节点，边，权重       n=4;//假设4个节点       int dist[MAXN][MAXN];      int path[MAXN][MAXN];      // 初始化      for (int i = 0; i < n; i++) {          for (int j = 0; j < n; j++) {              if (i == j) {                  dist[i][j] = 0;              } else {                  dist[i][j] = INF;              }          }      }             // 添加边（测试输入）       dist[0][1] = 3;      dist[0][2] = 6;      dist[1][2] = -2;      dist[2][3] = 2;      dist[3][0] = 1;            // 运行算法      floyd(n, dist, path);            // 输出结果      cout << "从0到3的最短路径：" << endl;      cout << "距离: " << dist[0][3] << endl;      cout << "路径: ";      print_path(0, 3, path);      cout << endl;      return 0;  }







六、负权环问题



负权环（回路）

Floyd算法可以处理负权边，但是不能处理负权回路。

什么是负权回路？

负权回路是有向图中从某节点出发回到自身的路径，所有边的权值之和为负数（无向图中负权边直接构成负环）。例如路径 1→2→3→1 权值和为 -2，则该回路为负环。

原因是：负权回路会导致路径长度可以无限减小，破坏了 “最短路径存在且有限” 的前提，进而让算法的核心逻辑（松弛操作）失去意义。



比如下面的例子:

我们使用以下有向图（顶点数为 4）：

顶点: 0, 1, 2, 3  边与权值:  0 -> 1: 3  0 -> 3: 5  1 -> 2: -2  2 -> 3: 1  3 -> 1: -1





初始距离矩阵 D⁽⁰⁾

我们用 D[i][j] 表示从 i 到 j 的当前最短距离估计。INF 表示不可达（这里用 ∞ 表示）。

D⁽⁰⁾0123
003∞5
1∞0-2∞
2∞∞01
3∞-1∞0

解释：

  • 对角线为 0（自己到自己的距离）。

  • 有直接边的填入权值（如 D[0][1]=3）。

  • 无直接边的填入 ∞。

如果按照上面的构造方式构造，可以得到下图的最终结论

D⁽⁴⁾（最终结果）0123
001-12
1∞-2-4-1
2∞0-21
3∞-3-5-2



我们检查最终矩阵的主对角线：



  • D[0][0] = 0

  • D[1][1] = -2 < 0

  • D[2][2] = -2 < 0

  • D[3][3] = -2 < 0



结论：图中存在负权回路。因为从顶点1、2、3到它们自己的“最短路径”变成了负数，这意味着可以无限绕行某个环使路径权值无限减小。在实际应用中，最短路径问题对于这样的图是无解的。



Floyd 算法虽然不能在负环存在时计算有效最短路径，但可以检测负环（通过判断 dist[u][u] < 0）

这是因为负环会让节点自身到自身的路径长度被松弛为负数。但检测到负环后，算法无法修正结果，只能提示 “该图存在负环，最短路径无意义”。





【参考代码】—带负权回路检测的Floyd算法

#include <iostream>  #include <climits>  using namespace std;   const int MAXN = 100;  const int INF = 1e9;    // Floyd算法：检测负权回路  bool floyd(int n, int dist[MAXN][MAXN]) {      // 初始化：确保对角线为0      for (int i = 0; i < n; i++) {          dist[i][i] = 0;      }            // Floyd算法核心      for (int k = 0; k < n; k++) {          for (int i = 0; i < n; i++) {              if (dist[i][k] == INF) continue;              for (int j = 0; j < n; j++) {                  if (dist[k][j] == INF) continue;                  if (dist[i][j] > dist[i][k] + dist[k][j]) {                      dist[i][j] = dist[i][k] + dist[k][j];                  }              }          }      }            // 检测负权回路：如果存在dist[i][i] < 0，则有负权回路      for (int i = 0; i < n; i++) {          if (dist[i][i] < 0) {              return true;  // 发现负权回路          }      }            return false;  // 没有负权回路  }    // 示例使用  int main() {      int n = 4;      int dist[MAXN][MAXN];            // 初始化      for (int i = 0; i < n; i++) {          for (int j = 0; j < n; j++) {              dist[i][j] = INF;          }      }            // 添加边(包含负权回路)      dist[0][1] = 3;      dist[0][3] = 5;      dist[1][2] = -2;      dist[2][3] = 1;        dist[3][1] = -1;              // 运行算法并检测负权回路      bool flag = floyd(n, dist);            if (flag) {          cout << "图中存在负权回路！" << endl;      } else {          cout << "图中不存在负权回路。" << endl;                    // 输出最短路径矩阵          cout << "最短路径：" <<endl;      	    for (int i = 0; i < n; ++i) {  	        for (int j = 0; j < n; ++j) {  	            cout << i << "→" << j << "：";  	            if (dist[i][j] == INF) cout << "INF"<<endl;  	            else cout << dist[i][j] <<endl ;  	        }  	        cout << endl;  	    }      }            return 0;  }



作者:亿万年的星光 分类:算法 浏览: