Floyd-Warshall 多源最短路
图算法 · 全源最短路径（任意两点）
一次求出所有点对的最短路
Dijkstra、Bellman-Ford 都是单源最短路——从一个起点出发。可有时我们想知道 任意两点之间的最短距离（比如任意两城市间的最短车程）。挨个点跑一遍单源当然行，但 Floyd-Warshall 用一张距离矩阵+ 三行循环，优雅地一次算出全部。
Floyd 怎么做
用矩阵 dist[i][j] 存「i 到 j 当前已知的最短距离」，初始就是邻接矩阵（有直接边取边权，没有则 ∞，自己到自己为 0）。然后逐个把每个点 k 试作中转点：对每一对 (i, j)，如果「i 先到 k，再从 k 到 j」比「i 直接到 j」更短，就更新 dist[i][j]。三层循环 for k / for i / for j，跑完就得到所有点对的最短距离。
下面固定一张 4 个点的有向带权图。点「下一步」逐步看：每选定一个中转点 k，它所在的行与列高亮；对每个候选单元 (i,j)（琥珀环），比较它与「两个黄色源单元之和」dist[i][k]+dist[k][j]——更短就变绿更新。走到底，矩阵里就是任意两点的最短距离。右侧代码随每一步同步高亮。
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 3 | 6 | ∞ |
| B | ∞ | 0 | 2 | 4 |
| C | ∞ | ∞ | 0 | 1 |
| D | 5 | ∞ | ∞ | 0 |
距离矩阵初始化为邻接矩阵（对角 0，有边取权，其余 ∞）
1function floyd(adj: number[][], n: number): number[][] {
2 const dist = adj.map((row) => [...row]);
3 for (let k = 0; k < n; k++) {
4 for (let i = 0; i < n; i++) {
5 for (let j = 0; j < n; j++) {
6 if (dist[i][k] + dist[k][j] < dist[i][j]) {
7 dist[i][j] = dist[i][k] + dist[k][j];
8 }
9 }
10 }
11 }
12 return dist;
13}
n4
中转 k-
已更新0
1 / 19
为什么三重循环、k 在最外层就对？这其实是动态规划：做完前 k 个中转点，dist[i][j] 就是「只允许经过前 k 个点中转」的最短路；加入第 k 个点后取 min，逐步放开限制直到允许所有点。复杂度 O(V³)——点少时简单又全面，还能处理负权边（无负环）。
Floyd vs 单源最短路
Dijkstra / Bellman-Ford：单源，一次一个起点；稀疏图上跑 V 次也常更快。
Floyd（本页）：全源，一次算出所有点对；
Floyd 的距离矩阵思路，正是动态规划在网格上填表的缩影。
Floyd（本页）：全源，一次算出所有点对；
O(V³)、代码极短，稠密小图首选，是「矩阵 DP」的经典范例。Floyd 的距离矩阵思路，正是动态规划在网格上填表的缩影。
想复习单源最短路，回看 Dijkstra 最短路（正权贪心）与 Bellman-Ford 最短路（负权松弛）——三页合起来就是最短路问题的完整版图。