前言
前两篇文章中介绍了 BFS（地毯式搜索）和 Dijkstra（精明导航）。它们都有一个共同点：以自我为中心。
也就是说，这两种算法都是“单源”（Single-Source）的。它们只能算出：
但在很多时候，作为研究者，我们想拥有“上帝视角”。我们不想只知道“某个主角”的社交圈，我们想瞬间知道这个圈子里，任意两个人（张三和李四、王五和赵六...）之间的最短路径。
这时候，如果你对全班 50 个人每个人都跑一遍 Dijkstra，代码会写得很累。
Floyd-Warshall 算法，它用一种极其“暴力”却优雅的方式，一次性填满整个网络的距离矩阵。
1. 为什么要用 Floyd？（解决什么问题）
Floyd 算法解决的是 多源最短路径（All-Pairs Shortest Paths） 问题。
它的核心应用场景：
小团体全景分析：比如你要分析一个 20 人的恐怖分子核心小组，你需要知道他们内部任意两人的联络成本，从而找出最脆弱的环节。
网络直径与中心度：只要跑一次 Floyd，你就能得到一个完整的矩阵。
看每一行的和 —>算出每个人的接近中心性。
看矩阵里的最大值 —> 就是网络直径。
传递闭包：判断谁和谁是连通的，谁和谁是老死不相往来的。
2. 核心逻辑：疯狂的“中转站”
Floyd 算法的原理非常有意思，它利用了动态规划的思想，但我们可以用一个“买机票”的例子来秒懂它。
核心思想：
“两点之间，直线不一定最短。如果找个中间人（中转站），会不会更近？”
算法步骤（三层循环的暴力美学）：
想象我们有一个 N*N 的表格（矩阵），填满了所有人目前的直连距离。
第一轮尝试：
假设所有人只能通过 1号成员（张三） 进行中转。
第二轮尝试：
假设所有人可以通过 2号成员（李四） 进行中转。
第 N 轮尝试：
...直到把所有人都当做“中转站”试了一遍。
公式的通俗解释
3. 结果怎么解读？（距离矩阵）
Floyd 算法跑完后，你得到不是一个数，而是一个 距离矩阵（Distance Matrix）。
假设有 A, B, C 三个人：
解读：
对角线为 0：自己到自己的距离永远是 0。
查表即得：想知道 A 到 C 的距离？直接看第 1 行第 3 列 —>8。
不对称性：如果是有向图（比如微博关注），矩阵可能是不对称的（A 到 B 是 3，B 到 A 可能是无穷大）。
4. 有什么缺点？（致命警告）
Floyd 算法是典型的“用时间换方便”。它的缺点非常非常明显，甚至可以说是致命的。
缺点一：慢到令人发指
缺点二：空间占用大
它需要维护一个 N * N 的矩阵。如果是几万个节点，光存这个矩阵就能把内存撑爆。
5. 总结与 Python 实战
Floyd 算法是小规模网络分析的“核武器”。
什么时候用？
节点数很少（< 500 个）。
网络比较稠密（边很多，几乎大家都认识大家）。
你需要一次性计算出全员两两之间的距离。
什么时候别用？
Python NetworkX 代码示例：
import networkx as nx# 1. 建图（小规模）G = nx.Graph()G.add_edges_from([(1, 2), (2, 3), (3, 4), (1, 4)])# 2. 开启上帝视角 (Floyd)# NetworkX 会自动帮你处理好矩阵计算all_pairs = nx.floyd_warshall(G)# 3. 查看结果print("节点1到节点3的最短距离:", all_pairs[1][3])# 输出结果应该是 2 (路径 1-2-3 或 1-4-3)
结语
至此，我们的“最短路径三剑客”（BFS、Dijkstra、Floyd）已经全部集结完毕。
BFS：查户口（数人头）。
Dijkstra：跑导航（省成本）。
Floyd：上帝视角（全图打击）。
更多内容，敬请关注
