斯坦福算法专项课程Course2 week2内容回顾

这一周的内容主要介绍了Dijkstra算法。

Course 2 Week 1

Dijkstra’s Algorithm

Dijkstra算法是解决单源最短路径问题,来看下算法的输入输出:

  • Input:有向图$G=(V, E). (m=|E|, n=|V| ) $,每条边有非负边长$l_e$,一个源点$s$
  • Output: 对于每个节点$v$,计算$L(v)$,其中$L(v)$为$s$到$v$的最短路径长度

这里最重要的假设为$l_e \ge 0$。

来看下算法描述:

解释下算法,这里将节点分为$X$和$V-X$,前者为已经计算完结果的节点,后者为还未计算的节点,$A[s]$表示到$s$的最短距离,$B[s]$记录了最短路径。

Why It Works

这部分证明为什么Dijkstra算法计算出了正确的结果,即如下事实成立:

利用数学归纳法证明。

证明:

对于出发点$s$,由于边长非负,所以显然有$L(s) = A[s] = 0$,基本情形得证。

假设对于任意$v\in X$($X$为之前描述的已经计算的节点),$L(v) = A[v]$,在这一轮迭代中,选择$w^ \in V-X$加入$X$,相应的$v\in X$记录为$v^$,那么:

现在任取一条到达$w^$的路径,必然可以表示为$s\to y,y\in X,y\to z,z\in V-X,z\to w^$,如下图所示:

这里就要用到每条边都非负的假设了,由假设可得

所以

由于$A[v^]+l(v^,w^*)$是$s$到$V-X$中节点的最短距离,所以

这表示

Fast Implementation

这一部分介绍加速算法的方法。

之前的算法一共要进行$n$次循环,每次要访问$O(m)$条边,所以算法时间复杂度为$O(mn)$,老师介绍的方法是使用Heap,具体如下:

这里保持了两个不变量,一是堆中的元素为$V-X$,二是每个节点的值$Key[v]$为$s$到$v$的最短路径,这样每轮循环抛出Heap顶部的即可,但是要维持第二点,还需要进行如下更新:

从上图中可以看出,之所以要进行这样的更新,是因为对于任意的点$v$,$s$到$v$的最短路径可能经过这一轮添加的节点。