算法思想
符号约定
设 $w(u,v)$ 表示 $u$ 与 $v$ 之间的边的边权。$o, t$ 分别为源点、终点。
基本过程
维护集合 $P, Q$. $P$ 为已找到最短路的点，$Q$ 为剩余的点。最初，仅有源点 $o$ 位于 $P$ 内。设所有的点有标记 $L$，$L(o)=0$.
首先进行初始化：$\forall v \text{ adjacent to }o$, $L(v)=w(o,v)$.
迭代以下过程直至 $t$ 加入集合 $P$：
- 对所有 $Q$ 中已赋过 $L$ 值的元素 $u$，选出 $Q$ 中目前 $L$ 值最小的元素 $m$，并且将其移入集合 $P$.
- 如下更新与 $P$ 相连的所有元素的 $L$ 值：$\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\leq l < L(m)$. 然而，$l_0$ 描述的路径也是“前面都走 $P$ 中元素，最后一步到 $P$ 外”类型的路径，于是 $l_0$ **大于等于** $L(v_1)$，那么 $L(v_1)\leq l_0 < L(m)$，这与“$L(m)$ 值最小”是矛盾的。因此，$L(m)$ 就是所有到达 $m$ 的路径中，最短路的长度。
递归证明
由于初始化后，$P=\{o\}, L(o)=0$ 是满足“$P$ 中元素 $L$ 值即为最短路长”的性质，$\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