CSCI3160 T09 Floyd-Warshall全点对路径
课程：CSCI3160 Design and Analysis of Algorithms 本讲：T09 Floyd-Warshall全点对路径 · 原件 T09-Floyd-Warshall-未核-隐藏.pdf（本地课件） p.1–19 定位：以允许使用的中间顶点编号为动态规划层。 承接：L15 全点对问题、T06 附带恢复
p.1–3：同一个全点对问题【新】
p.1 标题，p.2 允许负边但没有负环，求所有源目标对；p.3 沿用七点图，a到g为−9，b到a不可达。图（p.3）：有向边决定可达性，表格按行源点、列终点记录，不能作对称矩阵处理。
p.4–6：状态第三维不是路径边数
p.4 Floyd–Warshall用O(V³)，对稠密图可优于二叉堆版Johnson的O(V³log V)界。p.5 给a到g编号1到7。p.6 定义Dk(i,j)：从i到j，只允许编号≤k的点作中间顶点的最小距离，端点编号不受该限制。
p.6 “only intermediate vertices with ids ≤ k.”
因此D0允许一条直接边，或同点空路径，不是“所有距离无穷”。p.6文字例子把D0(c,e)写∞、D4(c,e)写−5，与图中c→e权−1以及后续表不符；正确两者均为−1。a→e的值则在k3变1，直到k7才变−6。
p.6 对 a→e 的每层值为 k=0,1,2 时 ∞，k=3,4,5,6 时1，k=7 时−6；另一项 D0(c,d)=−2 与直接边一致。p.4 还比较非负图反复 Dijkstra 和一般图 Johnson：使用课堂二叉堆实现时二者总界都是 O(V(V+E)log V)，本讲 DP 在 E=Θ(V²) 时去掉该界的对数因子。
p.7–9：是否使用新加入的中间点
p.7 初始化对角0、直接边权、其余∞。递推：
p.8 若某条最短路不经过k，第一项就达到它；p.9 若经过k，无负环保证可选一条简单最短路，k只需出现一次，分成i→k和k→j，两段中间点均≤k−1且分别最优。两项各代表合法走法，所以取小值恰为目标，不会只是某个不完整的上界。
原页两道 Think 的答案都来自最优性：若所选最短路不经过 k，却第二项严格更小，第二项给出更好的合法走法，删去非负环后得到不更长的路径，与最优矛盾；经过 k 的情形同理，第一项不能严格更小。无负环意味着重复 k 之间的闭合走法权重非负，删除不会变差；两段任何一段不最优都能替换，保持允许的中间点集合并降低总长，也与最优矛盾。
p.10–12：初始化与第一层
p.10 n³个三维状态，每个O(1)工作；按k从小到大、每层枚举所有i,j。p.11 初始有限非对角项为ab1、ad−6、bc1、cd−2、ce−1、dg−3、ed5、fe1、gf2。p.12 k1允许a为中间点，但其他点不能到a，所以没有改善。
p.11 初始化完整矩阵（p.12 的 k=1 与它完全相同）：
| 源\目标 | a | b | c | d | e | f | g |
|---|---|---|---|---|---|---|---|
| a | 0 | 1 | ∞ | -6 | ∞ | ∞ | ∞ |
| b | ∞ | 0 | 1 | ∞ | ∞ | ∞ | ∞ |
| c | ∞ | ∞ | 0 | -2 | -1 | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | -3 |
| e | ∞ | ∞ | ∞ | 5 | 0 | ∞ | ∞ |
| f | ∞ | ∞ | ∞ | ∞ | 1 | 0 | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | 2 | 0 |
p.13–15：允许 b、c、d
p.13 k2得ac=ab+bc=2。p.14 k3得ae=ac+ce=1、bd=bc+cd=−1、be=bc+ce=0；ad原为−6，比经过c的0更好，保持。p.15 k4新得ag=−9、bg=−4、cg=−5、eg=2，其余保持。这时虽能到g，却还不允许g作中间点，不能立即用g→f继续走。
以下依次是 p.13、14、15 的完整矩阵；未改善格继承上一层。
k=2，允许 b 及之前顶点作中间点
| 源\目标 | a | b | c | d | e | f | g |
|---|---|---|---|---|---|---|---|
| a | 0 | 1 | 2 | -6 | ∞ | ∞ | ∞ |
| b | ∞ | 0 | 1 | ∞ | ∞ | ∞ | ∞ |
| c | ∞ | ∞ | 0 | -2 | -1 | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | -3 |
| e | ∞ | ∞ | ∞ | 5 | 0 | ∞ | ∞ |
| f | ∞ | ∞ | ∞ | ∞ | 1 | 0 | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | 2 | 0 |
k=3，允许 c 及之前顶点作中间点
| 源\目标 | a | b | c | d | e | f | g |
|---|---|---|---|---|---|---|---|
| a | 0 | 1 | 2 | -6 | 1 | ∞ | ∞ |
| b | ∞ | 0 | 1 | -1 | 0 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | -2 | -1 | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | -3 |
| e | ∞ | ∞ | ∞ | 5 | 0 | ∞ | ∞ |
| f | ∞ | ∞ | ∞ | ∞ | 1 | 0 | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | 2 | 0 |
k=4，允许 d 及之前顶点作中间点
| 源\目标 | a | b | c | d | e | f | g |
|---|---|---|---|---|---|---|---|
| a | 0 | 1 | 2 | -6 | 1 | ∞ | -9 |
| b | ∞ | 0 | 1 | -1 | 0 | ∞ | -4 |
| c | ∞ | ∞ | 0 | -2 | -1 | ∞ | -5 |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | -3 |
| e | ∞ | ∞ | ∞ | 5 | 0 | ∞ | 2 |
| f | ∞ | ∞ | ∞ | ∞ | 1 | 0 | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | 2 | 0 |
p.16–18：最后三层与完整结果
p.16 k5通过e得fd=1+5=6、fg=1+2=3。p.17 k6通过f得gd=2+6=8、ge=2+1=3。p.18 k7允许g中转，a到e可用−9+3=−6，a到f为−9+2=−7。最终矩阵如下：
| 源\目标 | a | b | c | d | e | f | g |
|---|---|---|---|---|---|---|---|
| a | 0 | 1 | 2 | −6 | −6 | −7 | −9 |
| b | ∞ | 0 | 1 | −1 | −1 | −2 | −4 |
| c | ∞ | ∞ | 0 | −2 | −2 | −3 | −5 |
| d | ∞ | ∞ | ∞ | 0 | 0 | −1 | −3 |
| e | ∞ | ∞ | ∞ | 5 | 0 | 4 | 2 |
| f | ∞ | ∞ | ∞ | 6 | 1 | 0 | 3 |
| g | ∞ | ∞ | ∞ | 8 | 3 | 2 | 0 |
图（p.11–18）：红色数字表示本层新改善。元素：中间点层数和行列源目标是三个不同索引。看什么：不更新的格也是本层结果的一部分，不能漏抄继承值。
p.16 与 p.17 的完整中间层也保留如下，最终 k=7 已在上表。
k=5
| 源\目标 | a | b | c | d | e | f | g |
|---|---|---|---|---|---|---|---|
| a | 0 | 1 | 2 | -6 | 1 | ∞ | -9 |
| b | ∞ | 0 | 1 | -1 | 0 | ∞ | -4 |
| c | ∞ | ∞ | 0 | -2 | -1 | ∞ | -5 |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | -3 |
| e | ∞ | ∞ | ∞ | 5 | 0 | ∞ | 2 |
| f | ∞ | ∞ | ∞ | 6 | 1 | 0 | 3 |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | 2 | 0 |
k=6
| 源\目标 | a | b | c | d | e | f | g |
|---|---|---|---|---|---|---|---|
| a | 0 | 1 | 2 | -6 | 1 | ∞ | -9 |
| b | ∞ | 0 | 1 | -1 | 0 | ∞ | -4 |
| c | ∞ | ∞ | 0 | -2 | -1 | ∞ | -5 |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | -3 |
| e | ∞ | ∞ | ∞ | 5 | 0 | ∞ | 2 |
| f | ∞ | ∞ | ∞ | 6 | 1 | 0 | 3 |
| g | ∞ | ∞ | ∞ | 8 | 3 | 2 | 0 |
p.19：附带恢复与空间压缩
p.19 提示piggyback。补充做法：初始直接边(i,j)置next[i][j]=j，不可达空；严格因k改善时令next[i][j]=next[i][k]。从s不断走next[current][t]即可恢复到t的路；相等时不改，避免无意义零环选择。也可存前驱并从终点倒追。
若明确要每个源点一棵树，可保存 pred[s][v]：直接边初始设为 s；经 k 严格改善时设 pred[i][j]=pred[k][j]。最后对固定 s，把每个可达且 v≠s 的 v 挂到 pred[s][v] 下，不可达点不编造路径；逐个源点输出这些父边即可，最多 O(n²) 条输出边。
距离只依赖前一层，空间可用O(n²)；无负环时D(k,k)=0，在k这一轮D(i,k)、D(k,j)不会严格变小，所以可原地更新。必须k最外层，i,j在内层；任意交换三重循环顺序没有同样的状态保证。实际用有限整数代表∞时须先判可达再相加，防止溢出造出假路径。该实现细节为补充，不追加到主课记忆。
补充：状态限制只管中间点，端点不用排队获准。 自取三个编号1、2、3，边3→1权2、1→2权4、3→2权9。D₀(3,2)=9，因为直接边没有中间点；允许1作中间点后，D₁(3,2)=min(9,2+4)=6。源点3与目标2都大于当前k=1，完全合法。k既不是“最多几条边”，也不是“只能访问编号不超过k的所有顶点”。
恢复路径时，改善3→2是经1完成的，故 next[3][2]=next[3][1]=1；再查询 next[1][2]=2，走出3→1→2，长度6。记录的是第一跳，不是永远直接存当前k；因为到k的子路径也可能含更早中间点。
自测：为什么 i,j 两层可以互换，k 却不能随意放里面？
固定k后，每个格只使用“上一层允许1…k−1”的答案。本讲无负环时，到k和从k的关键行列不会因允许k自身而改善，所以二维原地写入安全，i与j的枚举先后不重要。把k放里面则一个格可能用到别的格尚未完成同样中间点集合的值，原递推证明不再适用。
本讲核心考点
- （C 级 通识）中间顶点编号与边数约束不同。
- （C 级 通识）两类路径导出递推，k必须是外循环。
- （C 级 通识）逐层矩阵、O(V³)时间与O(V²)空间、路径恢复。
附录
本讲所需过程已在正文展开。
来源与证据
-
本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
-
原件：T09-Floyd-Warshall-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。
-
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
-
发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。
-
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
-
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。