一、算法说明

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

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

二、核心思想

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)

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)

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)

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)

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)

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 表示不可达（这里用 ∞ 表示）。

解释：

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

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

• 无直接边的填入 ∞。

一、核心思想

1. 贪心策略：每次从未确定最短路径的节点中，选择距离源节点最近的节点，将其标记为 “已确定”；

2. 松弛操作：以该节点为中介，更新其邻接节点到源节点的距离；

3. 重复上述步骤，直到所有节点都被标记为 “已确定”。

二、算法步骤（以无向带权图为例）

1. 初始化：

• 距离数组 dist[]：dist[s] = 0（源节点到自身距离为 0），其余节点 dist[i] = ∞（无穷大）；

• 标记数组 visited[]：所有节点初始为 false（未确定最短路径）；

• 优先队列（小顶堆）：存储 (当前距离, 节点)，初始入队 (0, s)。（朴素解法不使用优先队列）

2. 迭代求解：

• 取出优先队列中距离最小的节点 u，若 u 已访问则跳过；

• 标记 u 为已访问（visited[u] = true）；

• 遍历 u 的所有邻接节点 v，若 dist[v] > dist[u] + 权值(u,v)，则更新 dist[v] = dist[u] + 权值(u,v)，并将 (dist[v], v) 入队；

3. 终止条件：优先队列为空，此时 dist[] 数组存储源节点到所有节点的最短路径。（朴素解法不使用优先队列）

【题目描述】

【输入】

【输出】

【输入样例】

5 5  1 2  2 3  3 4  4 5  5 1

【输出样例】

1 5 4 3 2 1

【提示】

Code::Blocks 是一款免费、开源且跨平台的 C/C++ 集成开发环境。它支持 Windows、Linux 和 macOS 等多种操作系统，核心特点是轻量快速、纯专注于 C/C++ 开发，并内置了对多种编译器（如 GCC、MinGW、Clang）的支持，是初学者和学习 C/C++ 编程的常用工具之一。

官网地址：https://www.codeblocks.org/

一、下载

点击左侧的”Downloads“或者点击下载地址：  https://www.codeblocks.org/downloads/

如果上面的打不开，可以使用网盘下载：

codeblocks-25.03mingw-setup.exe: https://url47.ctfile.com/f/64055047-8513804238-913cef?p=7381 (访问密码: 7381)

点击”Download the binary release“

这里选择的版本是codebloscks-25.03mingw-setup.exe，然后点击Sourceforge.net进行下载

然后就会跳转到  https://sourceforge.net/projects/codeblocks/

就开始下载了，如果没有下载，可以点击左侧的”Download“

二、安装

下载后可以看到安装程序，双击运行。

双击后，点击”Next“按钮

这里点击”I Agree“

下一步点击”Next“

这里可以选择其他盘符，然后点击‘Install”

安装过程：

这里点击“Yes”

然后点击“Next”

这一步点击“Finish”

等待一段时间后就可以看到Code::Blocks运行了