c++怎么实现弗洛伊德算法求最短路径_c++ 动态规划与邻接矩阵更新【案例】

弗洛伊德算法必须以k为最外层循环，因状态转移依赖disti和distk在当前轮次已被正确更新；初始化需设disti=0、有向边权值、其余为安全INF（如0x3f3f3f3f），并判INF再更新以防溢出。

弗洛伊德算法的核心是三重循环更新 dist[i][j]

它不依赖起点或终点预设，而是穷举所有中间点 k，检查是否通过 k 能让 i → j 更短。关键不是“怎么初始化”，而是“为什么必须按 k 为最外层循环”。如果把 i 或 j 放最外层，dist[i][k] 和 dist[k][j] 可能还没被当前轮次更新过，导致路径拼接失效。

初始化时，dist[i][i] = 0，有向边 (u, v, w) 对应 dist[u][v] = w，其余设为一个足够大的数（如 INT_MAX / 2，避免加法溢出）。

• INT_MAX 直接参与加法易溢出，用 INT_MAX / 2 更安全
• 图中含负权边可运行，但含负权环时，dist[i][i] 最终会为负 —— 这是检测负环的依据
• 节点编号建议从 0 开始，避免数组越界和偏移计算错误

邻接矩阵更新要防止整型溢出和无效路径叠加

核心更新语句是：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。但若 dist[i][k] 或 dist[k][j] 仍是初始大值，直接相加会溢出。必须先判断有效性：

if (dist[i][k] != INF && dist[k][j] != INF) {
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

否则哪怕逻辑上不可达，数值上也会因溢出变成极小负数，污染后续结果。

• 不要用 == INT_MAX 判断“不可达”，浮点或大数运算后可能失真；统一用自定义常量 INF
• 更新顺序不能交换：必须是 k 在最外层，否则不是 Floyd，而是错误的松弛顺序
• 空间复杂度固定为 O(n²)，无法像 Dijkstra 那样用堆优化；适合 n ≤ 500 的稠密图

动态规划视角下，dist[k][i][j] 的含义容易被误解

教材常说“dist[k][i][j] 表示只允许经过前 k 个节点时 i→j 的最短距离”，但这只是教学抽象。实际代码中根本没存三维数组 —— 它被压缩进二维并复用，靠 k 循环顺序保证状态转移正确。真正发生的是：每轮 k 结束后，dist[i][j] 已包含所有经节点 0..k 的最短路。

• 没有显式维度 k，所以不能在循环中随意访问 “上一轮” 的 dist[i][j]
• 不能把 dist[i][j] 更新写成 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 之外的形式（比如加条件跳过某些 k），会破坏 DP 状态定义
• 若需输出路径，得额外维护 next[i][j] 记录中转点，每次更新 dist 时同步更新

常见报错：runtime error: signed integer overflow 或全为 INF

前者几乎全是没判 INF 就做加法；后者常见于输入没读进邻接矩阵（比如节点编号从 1 开始却往 [0][0] 写）、或忘了设 dist[i][i] = 0。还有一种隐蔽错误：用 memset(dist, 0x3f, sizeof dist) 初始化，但 0x3f3f3f3f 是常用 INF 值，而若误写成 0x7f7f7f7f，它接近 INT_MAX，加法极易溢出。

• 推荐初始化方式：

  const int INF = 0x3f3f3f3f;
  for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
          dist[i][j] = (i == j) ? 0 : INF;
      }
  }

• 调试时打印几组 dist[0][*] 或 dist[*][n-1]，比看全矩阵更高效
• 算法本身不处理离散节点名（如字符串 ID），必须先映射为 0..n-1 整数索引

实际写的时候，最易忽略的是溢出防护和节点编号对齐——这两点出错，结果看起来“差不多”，但一换数据就崩。