Dijkstra正确性证明
Dijkstra算法的本质
如果你有思考“为什么”的习惯，就一定会发现，Dijkstra 的本质就是动态规划 + BFS 。松弛操作实际上就类似于动态规划中的状态更新。
设 \(f(u)\) 为 \(s\) 至 \(u\) 的最短路径（ \(s\) 为源点，下文同）。显然，状态转移方程为：
\[f(u)=min_{v\in fathers} f(v)+w_{u,v} \]其中，\(fathers\) 表示所有点 \(v\) 使得存在边 \(e=v\to u\) 。\(w_{u,v}\) 则表示该边的权。
这个状态转移方程是显然的，是非常经典的“退一步思考”，即思考点 \(u\) 是父节点中哪个点来的。既然我们求的是最短路，当然是能让整条路径最小的那一点。
而 Dijkstra 中，则引入了一切别的策略，本质上都只是优化。
正文
好了，实际上前文和正文都没关系，只是想要分享一下我对于一个算法的理解。
我们重新回忆算法每一步都干了什么：
- 在未确定最短路集合 \(T\) 中，选择估计最短路最短的点，将其移动至已确定最短路集合 \(S\) 中。
- 利用此点，更新邻近的点（松弛）。
我们无非就是需要证明，每次从 \(T\) 集合中拿出的点的估计最短路 $ dis(u) $ 与实际最短路 \(D(u)\) 相等。
使用反证法，假设此结论不成立，设 \(e\) 点是第一个从 \(T\) 点中拿出而 \(dis(e)\not= D(e)\) 。我们知道，估计最短路一定大于或等于实际最短路，即 $ dis(e)\ge D(e) $。
整理，得 $ dis(e) \gt D(e) $ 。
首先讨论一下第一个点能否不满足此结论。
算法刚开始，$ T $ 的每个点都为 $ +\infty $ 。随后，$ T_s $ 被修改为 0 。
那么，第一次拿出的点一定是 $ s $ 。$ dis(s)=D(s)=0 $ ，满足结论，即 $ e\not=s $ 。
接下来讨论不存在 $ s\to e$ 的路径时（即 \(D(s)=+\infty\) 时），是否满足结论：
此算法的 $ T_e $ 与 \(dis(e)\) 的更新依赖于父节点的松弛操作。
若父节点也未曾更新，\(T_e\) 与 $ dis(e) $ 也都未更新，$ dis(e)=D(e)=+\infty $ 。
若父节点更新过，意味着父节点的父节点也会有更新。不断追溯，发现，最初的更新来源于源点。
也就是说，若父节点更新，是从源点开始一路更新到父节点。那么意味着父节点存在一条路径 $ s \to father $。
若 $ e $ 点的父节点存在路径，那么 $ e $ 点也一定存在一条路径 $ s \to father \to e $ 。与讨论条件矛盾。
所以，若 \(e\) 点不存在与 $ s $ 点的路径时，结论成立。
也就是说 $ e $ 点一定存在一条路径 $ s\to e $ 。
那么讨论一下该路径的性质。
因为 $ e $ 是第一个出错的点，所以在此之前，所有 $ u \in S $ 都满足 $ dis(u) = D(u) $ 。
若所有 \(s \to e\) 的路径上的所有点都满足 $ u \in S $ ，显然 $ dis(e)=D(e) $ 与假设矛盾。
所以一定有一条路径 \(s \to x \to y \to e\) ，其中，$ y $ 是路径上第一个属于 $ T $ 的点。那么 $ x $ 就一定满足 $ x \in S $ 。
刚才已经提到，$ x $ 一定满足 $ dis(x) = D(x) $ 。此时会更新 $ y $ 。可以证明，当 $ e $ 被取走时，$ dis(y)=D(y) $。
\[dis(y)=D(y) \le D(e) \lt dis(e) \]但是因为过程 1 的条件，$ e $ 被取走时， $ e $ 一定是估计最短路最小的，而 $ y $ 没有取走，在比较范围内，所以一定有 $ dis(y) \ge dis(e) $ 。
但此与前文不等式链相矛盾，所以假设不成立，命题得证。
本证明大部分都取自 OI Wiki .
标签：短路,路径,算法,更新,正确性,Dijkstra,节点,dis From： https://www.cnblogs.com/liserver/p/18352518