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

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

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

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

来看下算法描述：

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

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

$L(v) =A[v],\forall v\in V$

利用数学归纳法证明。

证明：

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

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

$\begin{aligned} B[w^*]&= B[v^*]u(v^*,w^*) \\ A[w^*]&= A[v^*]+l(v^*,w^*) \end{aligned}$

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

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

$l(z ,w^*) \ge 0$

所以

$l(s, w^*) = l(s,y) +l(y,z) + l(z,w^*) \ge l(s,y) +l(y,z)$

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

$l(s, w^*) \ge l(s,y)+l(y,z) \ge A[v^*]+l(v^*,w^*) =A[w^*]$

这表示

$A[w^*] = L(w^*)$

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

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

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

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