算法思想

符号约定

设 $w(u,v)$ 表示 $u$ 与 $v$ 之间的边的边权。$o,t$ 分别为源点、终点。

基本过程

维护集合 $P,Q$. $P$ 为已找到最短路的点，$Q$ 为剩余的点。最初，仅有源点 $o$ 位于 $P$ 内。设所有的点有标记 $L$，$L(o)=0$.

首先进行初始化：$\mathrm{\forall }v\text{ adjacent to }o$, $L(v)=w(o,v)$.

迭代以下过程直至 $t$ 加入集合 $P$：

• 对所有 $Q$ 中已赋过 $L$ 值的元素 $u$，选出 $Q$ 中目前 $L$ 值最小的元素 $m$，并且将其移入集合 $P$.
• 如下更新与 $P$ 相连的所有元素的 $L$ 值：$\mathrm{\forall }u\text{ adjacent to }m$，如果 $u$ 尚无 $L$ 值或 $L(u)>L(m)+w(m,u)$，更新 $L(u)$ 为 $L(m)+w(m,u)$；否则保持 $L(u)$ 不变。

个人理解

对更新 $L$ 值过程的说明

其实是一个猴子选带王的过程

$L(v)$ 本质上是符合以下条件的路径中，最短路的长：$u_1,u_2,u_3,\cdots ,u_i,v$, where $u_{1,2,\cdots ,i}\in P$, $v$ 是待研究的点。（说人话：先走包含于 $P$ 中的路径，**最后一步** 跳到待研究点）每次扩张集合 $P$ 之后，都要问一问：如果以新加入点为跳板，$L$ 值能不能进一步减小？

注释：已经在 $P$ 中的结点具有“$L$ 值即为从 $o$ 到它最短路的长”的性质（将在下文说明理由），这使得我们可以通过 $L(u_i)+w(u,v)$ 来计算以 $u_i$ 为最后一步“跳板”的路径中，最短路的长。

通过这样的过程，我们可以保证，$L(v)$ 值维护了“先走$P$ 中路径，最后一步再到 $v$”的所有路径中，最短路的长度。

为什么 $P$ 中节点的 $L$ 值就是源点到它的最短路长度呢？

关键在于“选出 $Q$ 中 $L$ 值最小的元素移入 $P$”这一步！

下面证明：$Q$ 中 $L$ 值最小的元素 $m$，其 $L$ 值就是 $o$ 到 $m$ 的最短路的长度。

由于源点 $o\in P$，能够到达 $v$ 的路径可以分为两类：

• $u_1,u_2,\cdots ,u_i,v_1,v_2,\cdots ,v_j,m$, where $u_{1,2,\cdots ,i}\in P$, $v_1\notin P$
• $u_1,u_2,\cdots ,u_i,m$, where $u_{1,2,\cdots ,i}\in P$

也就是说，第二类路径除了 $m$ 外的点全都在 $P$ 中，而第一类路径只有开头的一小段在 $P$ 中，并于 $v_1$ 拐到 $P$ 外，后面的随意。

显然，对于 $L(m)$ 是第二类路径中路径长的最小值（这正是前文叙述的 $L$ 的含义）。对于第一类路径，假设存在一条路 $u_1,u_2,\cdots ,u_i,v_1,v_2,\cdots ,v_j,m$, where $u_{1,2,\cdots ,i}\in P$, $v_1\notin P$，且它的总长 $l$ 比 $L(m)$ 小。那么路径 $u_1,u_2,\cdots ,u_i,v_1$ 的长度 $l_0\le l<L(m)$. 然而，$l_0$ 描述的路径也是“前面都走 $P$ 中元素，最后一步到 $P$ 外”类型的路径，于是 $l_0$ **大于等于** $L(v_1)$，那么 $L(v_1)\le l_0<L(m)$，这与“$L(m)$ 值最小”是矛盾的。因此，$L(m)$ 就是所有到达 $m$ 的路径中，最短路的长度。

递归证明

由于初始化后，$P=\{o\},L(o)=0$ 是满足“$P$ 中元素 $L$ 值即为最短路长”的性质，$\mathrm{\forall }v\text{ adjacent to }o$, $L(v)=w(o,v)$ 的操作满足 $L$ 值的定义，迭代时选出 $Q$ 中目前 $L$ 值最小的元素 $m$，并且将其移入集合 $P$ 没有破坏“$P$ 中元素 $L$ 值即为最短路长”的性质；进而本次迭代中对 $L$ 的更新是合理的。

如是，每一次迭代都维护了这两个性质，递归证明成立。

边权为正

是为了使上一节中的论证成立。

Last modified on 2020-05-14