Mengzelev's Blog

算法导论学习笔记-单源最短路径

Word count: 1,148 / Reading time: 4 min
2018/10/30 Share

前备概念

环路

如果有负权重环路,问题比较大,因为你在环路里往死里转路径要多短有多短,这时候定义最短路径长度为负无穷。$\delta(u,v)=-\infty$

如果有正权重环路,那最短路径肯定不会走这个环路,所以不影响

如果有0权重环路,那这个环路等于没有,也不影响

初始化

$v.d$:最短路径估计

使用下面运行时间为$\Theta(V)$的算法来对最短路径估计和前驱结点进行初始化:

初始化操作的时间复杂度为$\Theta(V)$

松弛操作

松弛过程:试图改善从$s$到$v$的最短路径。
可能降低最短路径的估计值$v.d$并更新$v$的前驱属性$v.\pi$

松弛是唯一导致最短路径估计和前驱结点发生变化的操作

本章讨论的所有算法之间的不同之处是对每条边进行松弛的次数和松弛边的次序有所不同

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


这几条最好要背下来的,我觉得考试很容易考

为了方便记忆,po主尝试着用人话复述一遍:

  • 三角不等式性质:图里任意两个点和源点$s$构成一个三角形(可以退化为直线),有两边之和大于等于第三边
  • 上界性质:$v.d$撑死就是$\delta(s,v)$,不能再小了
  • 非路径性质:原话已经很人话了
  • 收敛性质:松弛前边的起点已求得最短路径,松弛后边的终点也将获得最短路径buff
  • 路径松弛性质:只要一条最短路径上的点是按松弛的,那么估计值就等于最短路径
  • 前驱子图性质:最短路径算完了,前驱子图是一颗根结点为$s$的最短路径树

Bellman-Ford算法

描述

  • 先将结点进行初始化
  • 对每条边进行$|V|-1$次松弛操作
  • 当存在负权重环路时会返回FALSE
  • 如果不存在负权重环路,则返回TRUE,每个结点的$v.d$即为源点$s$到该点的最短路径长度

伪代码

时间复杂度

$O(VE)$

正确性证明

用到了三角不等式 + 非路径性质 + 前驱子图性质

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

无环,因此没有负权重的环,对于任何结点,最短路径都是存在的

算法描述

先对DAG进行拓扑排序,按照拓扑排序的顺序对每个结点进行松弛操作

伪代码

时间复杂度

  • 拓扑排序(1): $\Theta(V+E)$
  • 初始化(2):$\Theta(V)$
  • 3~5行的循环(聚合分析):$\Theta(V)$
    总时间复杂度:$\Theta(V+E)$

正确性证明


精髓还是在于神奇的路径松弛性质,只要保证每条最短路径上边的松弛次序,就能得出算法终止时$v_i.d=\delta(s,v_i)$

应用

PERT图

Dijkstra算法

描述

  • 解决带权重的有向图上的单源最短路径问题
  • 要求所有边的权重都为非负值
  • 维护一组结点结合$S$,从源点$s$到该集合中每个结点之间的最短路径已经被找到
  • 使用贪心策略,每次都从结点集$V-S$中选择最短路径估计最小的结点$u$,然后更新与$u$相连的结点的最短路径估计值

伪代码

正确性证明

循环不变式:在算法第4~8行的while语句的每次循环开始前,对于每个结点$v\in S$,有$v.d=\delta(s,v)$

证明使用了反证法+最小数原理
关键步用到了收敛性质和权重非负的假设

时间复杂度

依赖于最小优先队列的实现

  • 数组遍历: $O(V^2)$
  • 二叉堆:$O(E\lg V)$
  • 斐波那契堆:$O(V\lg V+E)$

最短路径性质的证明

三角不等式

根据最短路径的定义即可得证

最短路径树性质

最短路径树的三条性质:

  • $v’$是图$G$中从源结点$s$可以到达的所有结点的集合
  • $G’$形成一棵根结点为$s$的树
  • 对于所有的结点$v\in V’$,图$G’$中从结点$s$到结点$v$的唯一简单路径是图$G$中从结点$s$到结点$v$的一条最短路径

未完待不会续

CATALOG
  1. 1. 前备概念
    1. 1.1. 环路
    2. 1.2. 初始化
    3. 1.3. 松弛操作
    4. 1.4. 最短路径和松弛操作的性质
    5. 1.5. Bellman-Ford算法
    6. 1.6. 描述
    7. 1.7. 伪代码
    8. 1.8. 时间复杂度
    9. 1.9. 正确性证明
  2. 2. 有向无环图(DAG)中的单源最短路径问题
    1. 2.1. 算法描述
    2. 2.2. 伪代码
    3. 2.3. 时间复杂度
    4. 2.4. 正确性证明
    5. 2.5. 应用
  3. 3. Dijkstra算法
    1. 3.1. 描述
    2. 3.2. 伪代码
    3. 3.3. 正确性证明
    4. 3.4. 时间复杂度
  4. 4. 最短路径性质的证明
    1. 4.1. 三角不等式
    2. 4.2. 最短路径树性质