【算法】单源最短路径

概要

• 单源最短路径问题产生的基础是，带权重的有向图
• 最短路径的含义是，两个结点之间的路径中，总权重和最小的路径
• 单源最短路径问题是指，在一个带权重的有向图中，找到从给定源结点到其它每个结点的最短路径

最短路径的几个变体

• 单目的地最短路径问题
• 单结点对最短路径问题
• 所有结点对最短路径问题

最短路径的最优子结构

• 引理 24.1 最短路径的子路径也是最短路径

负权重的边

• 如果图中不包含可以到达的权重为负值的环路，则所有结点的最短路径权重都有精确定义
• 如果包含权重为负值的环路，则环路中的结点最短路径权重都为负无穷

环路

• 一条最短路径不能包含权重为正值或负值的环路，如果路径中包含权重为 0 的环路，我们可以重复删除这些环路，直到得到一条不含环路的最短路径
• 所以在之后的讨论中我们假设最短路径都不包含环路

最短路径的表示

• 运行最短路径算法得到一个由 π 诱导的前驱子图，这个前驱子图是一颗最短路径树
• 树中的简单路径都是相应结点之间的一条最短路径
• 最短路径不一定是唯一的，最短路径树也不一定是唯一的

松弛操作

• 对一条边（u,v）松弛的过程是指，比较 v.d（v 的当前最短路径估计）与 u.d + w(u,v) 的值，根据比较结果决定是否更新 v.d
• 本章所有算法都要用松弛操作更新最短路径估计的值，各算法的区别只是松弛操作的次数和次序不同

最短路径和松弛操作的性质

• 三角不等式性质
• 上界性质
• 非路径性质
• 收敛性质
• 路径松弛性质
• 前驱子图性质

Bellman-Ford 算法

• Bellman-Ford 算法思路是对所有的边都进行一次松弛操作，循环 V 遍，用于解决一般情况下的单源最短路径问题（允许权重为负值）

• Bellman-Ford 算法会返回一个布尔值，当图中包含权重为负值的环路时，返回 FALSE，否则返回 TRUE

• 算法的性能为 O(VE)

• 引理 24.2 证明了在不考虑权重为负值的环路时，Bellman-Ford 算法中的循环可以将所有结点的最短路径估计 d 收敛为最短路径值

• 推论 24.3 说明了在不考虑权重为负值的环路时，Bellman-Ford 算法终止时，对所有结点 v，存在从 s 到 v 的路径当且仅当 v.d < ∞

• 定理 24.4 最终证明了算法的正确性

有向无环图中的单源最短路径问题

• 令我奇怪的是本节的算法居然没有自己的名字，本节的算法解决的是无环图中的单源最短路径问题，与 Bellman-Ford 算法相比是无法探测环路
• 算法的思路是先对图进行拓扑排序（所以无环是关键），在按照拓扑排序的次序对所有结点进行遍历，处理每个结点时对由该结点出发的所有边进行松弛操作
• 算法的执行时间为 O(V+E)，性能远远好于 Bellman-Ford 算法
• 定理 24.5 证明了该算法的正确性
• 本节算法的一个应用是在 PERT 图中分析关键路径（大概意思是一系列有前置关系的工作，权重为工作消耗的时间等成本，计算关键路径）

Dijkstra 算法

• Dijkstra 解决的是带权重的有向图上的单源最短路径问题，要求所有边的权重都为非负值
• 算法的思路是，将所有结点放入一个最小优先队列，遍历该队列，对每个结点的处理是对由该结点出发的所有边进行松弛操作
• 定理 24.6 证明了 Dijkstra 算法的正确性，用了循环不变式的方法反证，略复杂
• 推论 24.7 是说 Dijkstra 算法结束时，生成的前驱子图就是一颗最短路径树
• Dijkstra 算法的性能主要取决于所使用的最小优先队列的性能，如果使用斐波那契堆来实现，则可以将 Dijkstra 算法的运行时间改善到 O(VlgV+E)

差分约束和最短路径

线性规划

• 书中给出的线性规划的数学描述非常蛋疼，通俗的说，线性规划问题是在一组约束条件下，找到一个解使得目标函数的值最大

差分约束系统

• 将线性规划问题简化，将线性规划矩阵 A 的每一行包括一个 1 和一个 -1，其余所有项皆为 0，问题就成为一个差分约束系统
• 引理 24.8 说明了若 x 是差分约束系统的一个解，那么 x+d 也是该差分约束系统的解

约束图

• 将差分约束系统想象为一个带权重的有向图，图中的每条有向边对应 m 个不等式中的一个（差分约束系统的一行）
• 定理 24.9 证明如果约束图不包含权重为负值的环路，则最短路径能构成问题的一个可行解，如果包含权重为负值的环路，则没有可行解
• 数学果然还是要靠想象力

求解差分约束系统

• 可以用 Bellman-Ford 算法求解差分约束系统

最短路径性质的证明

三角不等式性质

• 引理 24.10 证明了三角不等式性质，实话说感觉不怎么需要证明，反证一下就能明白

最短路径估计值的松弛效果

• 引理 24.11 上界性质，比较好理解，归纳法证明
• 推论 24.12 非路径性质，通俗的说就是 s 到 v 之间不存在路径，那么 v.d 一直为无穷大
• 引理 24.13 感觉是废话，看松弛操作的定义就知道，一个连名字都没有的性质
• 引理 24.14 收敛性质，通俗的说就是对一条最短路径上的边 u ~ v 来说，如果对其进行松弛之前 u 已收敛，那么松弛后 v 就会收敛，关键在于 u ~ v 是最短路径上的边
• 引理 24.15 路径松弛性质，通俗的说就是在一条最短路径上，按照路径上结点的顺序对边进行松弛，则每松弛一条边，其所到达的结点就会收敛。与上面的引理是承接的。看到性质就猜到会用归纳法证明。

松弛操作与最短路径树

• 引理 24.16 关注的是 Gπ 诱导的根节点为 s 的有根树，重点在于在一系列松弛操作的过程中，Gπ 一直维持有根树的性质
• 引理 24.17 前驱子图性质，关注的是上条引理中提到的有根树是最短路径树，重点在于从 s 到任意结点的路径都是最短路径

感想

• 在数学领域，愚蠢才会限制一个人的想象力