某市交通管理局要为一款导航 App 提供数据支持。工程师小陈拿到的是一张 n 个路口、m 条道路的城市地图，每条路有通行时间。他的任务有两项：
任务一（全城地图）：回答"任意两个路口之间的最短通行时间"。用户可能随时查询任意一对起点和终点，总查询次数可能高达上万次。如果每来一个查询就跑一次 Dijkstra，就算 Dijkstra 再快也扛不住 —— 需要的是一张一次算好、永久可用的"全城最短距离表"。这就是 Floyd-Warshall 算法：三重循环，O(n³) 时间，把所有点对的距离一次性算清，之后每次查询都变成 O(1) 的查表。
任务二（备用路线）：对某些关键路口，导航需要准备一条"次优路线" —— 当主路线上某条路临时封路时，能立刻给出"第二短的走法"。小陈这才发现，很多题目问的不是"最短是多少"，而是"比最短长一点、但尽可能短的那条路是多少"，这就是 次短路问题。
小陈在实现次短路时踩了个坑：他本想"先算最短路，然后把最短路上的某条边删掉再跑一次最短路"，这样确实能求出与最短路不完全重叠的一条路径，但代码要跑很多次最短路，很慢。后来老张教他一个更优雅的做法：给每个点同时维护两个距离 —— dis1 表示最短距离、dis2 表示次短距离，在 Dijkstra 的松弛语句里同时更新这两个值。一次 Dijkstra 就把两张表全算出来了。
Floyd 管"所有点对"，次短路管"第二好" —— 两件事，两套工具。
💡 故事背后的算法思想
Floyd 的本质是动态规划：用 f[k][i][j] 表示"只允许经过前 k 个点作为中转时，i 到 j 的最短距离"。它的状态转移只有两句话：要么不用第 k 个点中转（沿用 f[k−1][i][j]），要么用第 k 个点中转（f[k−1][i][k] + f[k−1][k][j]）。取最小值即可。
次短路的本质是"多维护一维最优值"：最短路问题里每个点只记"最优值"，次短路问题里每个点记"最优值 + 次优值"。松弛时不但要考虑"能否刷新最优"，还要考虑"能否刷新次优"。这种"多维护几个候选值"的思想，在"第 K 短路"、"带去除条件的方案"等题目里反复出现。
两者的适用边界：Floyd 只适合 n ≤ 500 左右的小图（n³ 很快超时），但可以处理负权边和判负环；次短路必须保证边权非负（否则"次短"可能不存在）。