第 7 讲 · 最短通路与关键路径

带权图中，一条通路的长度是边权之和。最短路算法的区别，不在于代码长短，而在于图的结构和边权允许我们按什么顺序确定答案。

DAG 最短路就是沿依赖顺序做动态规划

有向无环图可以拓扑排序。设源点为 ss，按拓扑序处理顶点，对每条边 u→vu\to v 做松弛：

dist⁡(v)←min⁡{dist⁡(v),dist⁡(u)+w(u,v)}.\operatorname{dist}(v) \leftarrow \min\{\operatorname{dist}(v),\operatorname{dist}(u)+w(u,v)\}.

处理 vv 时，所有可能到达它的前驱已经处理完，因此 dist⁡(v)\operatorname{dist}(v) 可以定型。这里的顶点像动态规划子问题，有向边像状态依赖。

无权图用 BFS 按层扩展

把每条边权看成 1，BFS 从源点先访问距离 1 的点，再访问距离 2 的点。队列保证顶点按发现层次处理，因此第一次访问一个顶点时，走过的边数最少。BFS 树上从源点到每个顶点的树路径就是最短路。

Dijkstra 依赖非负边权

Dijkstra 维护源点到各顶点的暂定距离，每轮选择暂定距离最小的未确定顶点 uu，把它定型，再用 uu 的出边松弛邻居。

为什么可以定型？任何尚未发现的绕路都要先到达另一个未确定顶点；该顶点的暂定距离不小于 uu，再加非负边后不可能得到比 uu 更小的路径。

因此 Dijkstra 的前提是所有相关边权非负。出现负边时，已经定型的距离可能被后来的路径推翻；应改用 Bellman–Ford 等允许反复松弛的算法。若要计算所有点对最短路，可以使用 Floyd–Warshall。负圈可让路径权无限下降，此时“最短”本身不存在。

一道最短路题的手算顺序

  1. 写 d(s)=0d(s)=0，其他点为 ∞\infty；
  2. 每轮圈出暂定距离最小的点；
  3. 对它的每条出边计算“当前距离 + 边权”；
  4. 若更小，更新距离并记录前驱；
  5. 终点定型后沿前驱逆推整条通路。

只写最短距离不够；题目问“通路”时必须保留前驱。

工序网络把最短思路反过来求最长约束链

在工序流线图中，边表示活动及持续时间，顶点表示事件。正向计算事件最早发生时间：

ve(v)=max⁡u→v{ve(u)+w(u,v)}.ve(v)=\max_{u\to v}\{ve(u)+w(u,v)\}.

因为事件必须等待所有前置活动完成，所以取最大值。再从终点反向计算最迟发生时间：

vl(u)=min⁡u→v{vl(v)−w(u,v)}.vl(u)=\min_{u\to v}\{vl(v)-w(u,v)\}.

活动 u→vu\to v 的最早开始时间是 ve(u)ve(u)，最晚开始时间是 vl(v)−w(u,v)vl(v)-w(u,v)。二者相等时，该活动没有机动余量，是关键活动；从源点到终点由关键活动组成的最长通路就是关键路径。

“最长”并不表示故意拖延，而是整个项目工期受到这条依赖链约束：关键活动延误多少，项目至少延误多少。

评论