dijkstra 正确性证明

算法过程

定义 S 为已确定最短路的点的集合；\(dis_i\) 存储当前从源点 1 到 \(i\) 的最短路径。

初始状态： \(dis_1=0\)，\(dis_{2..n}=\) INF，S 为空。

1. 在未确定最短路的点中选出 \(dis\) 值最小的点 \(k\)，将 \(k\) 加入 S 集合。
2. 扩展 \(k\)。（扩展即为用 \(dis_k\) 更新与 \(k\) 相连的点的 dis 值）

重复 1、2 步骤，直到所有点都加入 \(S\) 集合。

正确性证明

已知：当前 \(S\) 中的节点都已进行扩展。
要证明：在未确定最短路的点中选出 \(dis\) 值最小的点 \(k\)，\(dis_k\) 就是源点到 \(k\) 的最短路。

证：
假设 \(dis_k\) 不为 \(k\) 的最短路，
在 \(k\) 的最短路径上找出第一个不在 \(S\) 中的点 \(p_i\), \(p_i \neq k\) （一定有这样一个 \(p_i\)；\(Path_k\)：1-...-\(p_i\)-...-k）；1...k 长度（真正最短路）\(\ge\) 1...p 长度（\(p\) 的最短路长度）
考察当前 \(dis[p_i]\) 的值，由于“当前 \(S\) 中的节点都已进行扩展，\(dis[p_i]\) 的值就是 \(p_i\) 的最短路，\(dis[p_i]<=dis[k]\)。
如果 \(dis[p_i]<dis[k]\) ，矛盾。
如果 \(dis[p_i]=dis[k]\)，可推出 \(dis[k]\) 为最短路，矛盾。