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

距离上次更新已经 2011 天了，文章内容可能已经过时。

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

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

这里最重要的假设为 $l_{e} \geq 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^{*}) \geq 0

所以

l (s, w^{*}) = l (s, y) + l (y, z) + l (z, w^{*}) \geq l (s, y) + l (y, z)

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

l (s, w^{*}) \geq l (s, y) + l (y, z) \geq A [v^{*}] + l (v^{*}, w^{*}) = A [w^{*}]

这表示

A [w^{*}] = L (w^{*})

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

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

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

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