1 算法概述
Floyd-Warshall算法是一种用于求解图中任意两点最短路径的经典动态规划方法。它通过逐步考虑“允许经过的中间顶点集合”来更新距离，最终得到所有点对之间的最短距离。由于写法简洁、结构清晰，它在图论与算法教学中具有很高的代表性。
1.1 问题定义
该算法研究的是带权图中的全源最短路径问题，即给定图中任意两个顶点，求从一个顶点到另一个顶点的最短路径长度。这里的“最短”通常指边权之和最小，而不是边数最少。若图中某两点之间不存在可达路径，则其距离通常记为无穷大。
1.2 核心思想
Floyd-Warshall算法的基本思路是：先从仅允许直接边连接的情况出发，再逐步把更多顶点作为中间节点纳入考虑。每加入一个新的中间顶点，就检查所有点对是否能借助该顶点形成更短路径，并据此更新距离矩阵。经过全部顶点的处理后，矩阵中的值即为最终答案。
1.3 适用范围
该算法适用于顶点数量较少到中等规模、但需要一次性求出全部点对最短路的情形。它不依赖单源出发，因此在需要批量查询距离时十分方便。
1.3.1 有向图与无向图
Floyd-Warshall算法既可用于有向图，也可用于无向图。在无向图中，一条边通常会在两个方向上同时生效，因此初始化时会同时更新双向距离；在有向图中，则按边的实际方向赋值即可。
1.3.2 带负权边图
该算法可以处理含负权边的图，只要图中不存在从任意点可达的负权环。负权边会被正常纳入转移过程，因此在一些无法使用只适合非负边的算法场景中，它具有明显优势。
1.3.3 不适用场景
当图规模很大时，Floyd-Warshall算法的时间与空间开销通常偏高。此外，若问题只需要单源最短路，使用该算法往往不如专门的单源算法高效。对于存在负权环且要求最短路值有明确意义的情形，该算法也无法直接给出有限结果。
2 算法原理
Floyd-Warshall算法本质上是一个三层递推的动态规划过程。它把“中间顶点是否可用”作为阶段变量，依次扩展可选范围，从而在有限轮次内完成全局最短路计算。
2.1 动态规划视角
从动态规划角度看，算法维护的是“在只允许使用前若干个顶点作为中间点时，任意两点间的最短距离”。随着允许范围扩大，旧状态会被新状态覆盖或改进。
2.1.1 状态定义
常见定义是设 d[k][i][j] 表示：在中间顶点只允许从编号不超过 k 的顶点中选择时，顶点 i 到顶点 j 的最短距离。这样，k 的增加就对应着状态空间的逐步放宽。
2.1.2 状态转移方程
转移关系通常写为：
d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j])
其含义是：从 i 到 j 的最短路，要么不经过第 k 个顶点，要么经过它一次并将路径拆成两段。这个式子构成了算法的核心。
2.2 中间顶点逐步引入
算法之所以有效，在于它把复杂的全局问题拆成了若干层局部更新。每一层只关注一个新增顶点，从而保证更新过程可控且易于实现。
2.2.1 顶点编号顺序
顶点通常按输入顺序或预先编号的顺序处理。编号本身并不影响最终正确性，只要每个顶点都被作为“新增中间点”考虑一次即可。编号顺序更多影响实现习惯，而非算法本质。
2.2.2 最短路的逐层更新
每轮引入一个中间顶点后，都要检查所有起点与终点组合，看是否能通过该顶点缩短路径。这样，已知最短路信息会不断被加强，最终收敛到完整答案。整个过程类似“层层扩展搜索范围”，但采用的是矩阵式递推，而非显式搜索。
2.3 矩阵表示方法
实现中，Floyd-Warshall算法通常以矩阵为核心数据结构。距离矩阵负责存储数值结果，前驱矩阵则用于恢复具体路径。
2.3.1 距离矩阵
距离矩阵 dist[i][j] 表示从 i 到 j 的当前已知最短距离。初始化时，直接边的权值会写入矩阵，不连通位置则设为无穷大。随后所有更新都围绕该矩阵展开。
2.3.2 前驱矩阵
前驱矩阵用于记录路径上的前一个顶点或中继信息。借助它，可以在求得最短距离后还原整条路径。不同实现中，前驱矩阵的定义略有差异，但目的都是支持路径恢复。
3 算法流程
Floyd-Warshall算法的流程相对固定，通常由初始化、三重循环更新和结果输出三部分组成。其实现简洁，逻辑上也较易验证。
3.1 初始化
初始化阶段决定了后续更新的起点。若初值设置不当，最终结果也会受到影响，因此这一环节非常重要。
3.1.1 自身距离设定
通常将 dist[i][i] 设为 0，表示顶点到自身的距离为零。这一设置是最短路计算中的基础条件，也有助于后续判断和更新。
3.1.2 边权赋值
对于图中每条边 u -> v，将 dist[u][v] 设为该边权值。若存在多条同向边，则通常保留较小权值作为初始值，以免影响最短路结果。
3.1.3 无穷大表示
对于当前未知或不可达的点对，矩阵中一般使用一个足够大的数作为“无穷大”标记。实现时需要注意避免该值在加法中产生溢出或误判，因此常配合条件判断使用。
3.2 三重循环更新
算法的核心部分由三层循环构成，分别枚举中间点、起点和终点。它是一个典型的动态规划遍历结构。
3.2.1 外层中间点循环
外层循环依次选择一个顶点作为新增中间点。每一轮都尝试利用该顶点改善任意点对之间的距离，并将更优结果写回矩阵。
3.2.2 内层起点循环
在固定中间点之后，需要枚举所有可能的起点。这样才能保证从任意源点出发的路径都能被检查到，不会遗漏潜在的更短路线。
3.2.3 终点循环
对每个起点，还要继续枚举所有终点，完成完整的点对更新。若 dist[i][k] + dist[k][j] 小于当前 dist[i][j]，则说明经由 k 可以获得更优路径，应立即替换。
3.3 结果输出
完成所有更新后，矩阵中的值即可直接作为任意两点之间的最短距离结果。若还维护了前驱信息，则还能进一步恢复具体路径。
3.3.1 最短距离查询
查询任意两点最短距离时，只需读取 dist[i][j] 即可。对于不可达点对，其值通常仍为无穷大，表示不存在可行路径。
3.3.2 路径恢复
路径恢复一般从终点反向追踪前驱信息，直到回到起点为止。也可以通过记录中继点递归展开路径。不同方案实现思路相近，关键在于更新距离时同步维护辅助信息。
4 正确性分析
Floyd-Warshall算法的正确性可以从动态规划的最优子结构和状态递推两方面说明。它依赖逐步扩展中间点集合，因此每一步更新都建立在已知最优结果之上。
4.1 最优子结构
任意一条最短路径如果经过某个中间顶点，那么它的前半段和后半段也应分别是对应子问题下的最短路径。否则，若某一段还能进一步缩短，整条路径也会变得更短，从而与“最短”矛盾。
4.2 递推有效性
算法的递推式在每一层都只比较“经过新增顶点”和“不经过新增顶点”两种情况，因此不会遗漏任何可能的最短方案。由于每轮处理后，允许的中间点集合只会扩大，不会缩小，所以旧结果始终是新结果的合法基础。
4.3 负权边条件
负权边不会破坏递推本身，但要求图中不能存在可达负权环。若存在负权环，最短路径长度可能不再有下界，路径可以通过环不断降低总权值，从而使“最短”失去明确意义。
4.4 负权环检测
在算法结束后，如果某个顶点 i 满足 dist[i][i] < 0，通常说明图中存在负权环，并且该环与 i 可达相关。这个性质常被用作负权环检测的依据，是该算法的重要附加功能之一。
5 复杂度分析
Floyd-Warshall算法的复杂度特征非常鲜明：实现简单，但代价较高。它适合换取代码简洁和全局查询能力，而不是追求极致性能。
5.1 时间复杂度
标准实现的时间复杂度为 O(n^3)，其中 n 是顶点数。三重循环分别遍历中间点、起点和终点，因此总操作次数随顶点数立方增长。
5.2 空间复杂度
若只保存距离矩阵，空间复杂度为 O(n^2)。若进一步维护前驱矩阵或其他路径恢复信息，仍通常保持在二次方量级，但常数会有所增加。
5.3 与其他最短路算法的比较
与单源最短路算法相比，Floyd-Warshall算法更擅长一次性求解全源距离，但在稀疏图上往往不占优势。与适合非负权图的算法相比，它能处理负权边，适用面更广；但相应地，运行成本也更高。对于需要大量点对查询的场景，它的预处理开销常常是可以接受的。
6 实现细节
Floyd-Warshall算法虽然思想统一，但在不同编程语言中的实现习惯略有差异。实际编写时，需要特别关注数值范围、初始化方式以及路径记录结构。
6.1 C++实现要点
C++中常用二维数组或 vector<vector<long long>> 存储距离矩阵。若边权较大，建议使用更宽的整数类型，并合理设置无穷大常量。更新时应先判断两段距离是否可达，避免无穷大相加带来的错误。
6.2 Python实现要点
Python代码通常较为简洁，适合直接用列表嵌套实现矩阵。由于 Python 的整数不易溢出，数值上较安全，但在 O(n^3) 复杂度下，性能可能成为瓶颈，因此更适合中小规模图。
6.3 Java实现要点
Java实现一般使用 long[][] 或 int[][] 存储矩阵，并配合 INF 常量表示不可达。编写时要注意数组下标和初始化细节，同时尽量减少循环内不必要的对象操作，以提升执行效率。
6.4 常见边界情况处理
实际应用中，图数据常包含多种边界情形。若不事先处理，可能导致初始化错误或结果偏差。
6.4.1 多重边
当两点之间存在多条边时，应保留权值最小的一条作为初始距离。这样可以保证后续更新建立在最优的直接连接基础上。
6.4.2 自环
自环边是否参与更新，取决于其权值及问题定义。若自环权值为负，需格外警惕负权环；若为非负，通常不会改变最短路结果，但仍可在初始化时按规则处理。
6.4.3 不连通图
对于不连通的点对，结果应保持为无穷大或其他约定标记。实现中只要正确初始化，这类情况通常会自然保留，不会被误更新为有限值。
7 应用场景
Floyd-Warshall算法在需要全面掌握图中距离关系时非常实用。它不仅能计算最短路，还常被作为图分析的基础工具。
7.1 网络通信
在网络拓扑分析中，该算法可用于评估节点之间的最短传输代价，帮助理解路由层面的距离结构。对于需要预先计算全部节点对代价的系统，它具有较强的实用性。
7.2 地图与交通规划
在道路网络、城市交通或站点连接模型中，Floyd-Warshall算法可用于分析任意两地之间的最优通行方案。尤其在节点规模不大、但查询频繁的情况下，它的统一预处理方式较为方便。
7.3 图分析与关系建模
在社交关系、依赖图或一般网络分析中，最短路径常用于衡量联系强度、层级深度或传播成本。该算法能够直接输出全局距离矩阵，因此常作为进一步分析的基础。
7.4 稠密图最短路问题
当图较为稠密时，边数接近顶点数平方，Floyd-Warshall算法的 O(n^3) 代价并不一定显得过高。相比频繁对每个源点重复运行单源算法，它有时反而更简洁直接。
8 变体与扩展
在基础最短路功能之外，Floyd-Warshall算法还可作多种扩展，适用于路径恢复、可达性分析以及带约束的图问题。
8.1 路径重建版
路径重建版通常在更新距离时同步记录中继点或前驱点。这样，除输出距离外，还能还原一条实际的最短路径。该扩展在导航、调度和可视化场景中尤其常见。
8.2 传递闭包相关应用
若将边的权值从数值距离改为布尔可达性，算法可转化为求图的传递闭包。此时关心的不是路径长度，而是“是否存在可达路径”。这一思路在关系推导与可达性判断中很常见。
8.3 带限制条件的扩展
在某些问题中，路径可能还要满足额外约束，例如限定经过点数、限定中继集合或限制某类边的使用。Floyd-Warshall算法可作为基础框架，再结合状态扩展或附加判定实现更复杂的目标。
8.4 与布尔矩阵运算的联系
从形式上看，Floyd-Warshall与布尔矩阵上的递推具有相似性：都通过“中间点”进行逐步合成。一个关注最小代价，另一个关注可达性，因此它们在结构上接近，在数学表达上也常被并列讨论。
9 相关算法
Floyd-Warshall算法与多种经典最短路算法关系密切。它们在适用图类型、处理边权范围和求解目标上各有侧重。
9.1 Dijkstra算法
Dijkstra算法用于单源最短路，通常要求边权非负。它在稀疏图和单次查询场景中效率较高，但不能直接处理负权边，因此与Floyd-Warshall算法形成鲜明对比。
9.2 Bellman-Ford算法
Bellman-Ford算法同样支持负权边，并可用于检测负权环。它也是单源最短路算法，但时间复杂度通常高于Dijkstra。与Floyd-Warshall相比，它更适合只关心一个起点的情况。
9.3 Johnson算法
Johnson算法面向全源最短路问题，常用于稀疏图。它通过重标定边权并多次运行单源最短路方法来完成计算，在图较大且较稀疏时，往往比直接使用Floyd-Warshall更高效。
9.4 Warshall算法
Warshall算法是Floyd-Warshall思想在可达性问题上的对应版本，主要用于计算传递闭包。它不处理数值权重，而是关注点对之间是否存在路径，属于同一思想框架下的不同应用。