讲一个小故逝
今天做到了一道很典的题目P1875，我发现我其实并不太会，然后在我看完了题解剽题解的屑以后，我发现我对 dijkstra 的理解仅仅停留在它的过程，而没有深入挖掘 dijkstra 的正确性以及它的本质等等。所以这篇文章会从另一个角度来看看 dijkstra。也许这是 dijkstra 的本质吧，还望各个巨佬多多指教 awa
Dijkstra 是啥
dijkstra 用于解决正边权图的单源最短路问题，这是模板题 Link。
背下来 dijkstra 的板子很简单因为我亲身试过，但是我们还是需要进一步了解它的原理，并且去了解它的妙处所在。
我们先达成共识一下，\(s\) 代表起点（或者说源点），\(dis(u)\) 代表 \(s\) 到 \(u\) 最短路长度，一开始 \(dis(s) = 0\)（从起点到它自己可不得是 \(0\) 嘛），除此之外的 \(dis(x) = INF(x\not= s)\)。记一条边 \((u, v, w)\) 为一条从 \(u\) 到 \(v\) 边权为 \(w\) 的边。
那么朴素的 dijkstra 怎么干活的嘞？朴素的 dijsktra 建立在一个归纳的基础上。比如说我们得到了最短路前 \((i - 1)\) 小的最短路值和点集，这个点集记为 \(S\)（这样说比较绕口，麻烦大家多读几遍 awa）。现在我们的任务就是，找到第 \(i\) 小的最短路。
这样的归纳基础在哪？一开始 \(i = 0\) 时点集是空的，\(i = 1\) 时我们就可以找到第 \(1\) 小的点 \(s\)，然后就可以把 \(s\) 这个点加入点集 \(S\) 当中去。
然后怎么归纳下去？我们就应该用 \(S\) 中的点去更新别的点的最短路了。当 \(i = 1\) 时集合 \(S\) 里只有 \(s\) 一个点，所以我们用 \(s\) 点更新别的点的最短路。最短路要满足这样一个三角形不等式。在求出所有的最短路后，对于任意一条边 \((u, v, w)\)，一定满足 \(dis(v) \le dis(u) + w\) 这个三角形不等式。这不难理解，否则我们可以更新 \(dis(v)\)。更新操作被称为松弛。所以我们可以遍历从 \(s\) 出发的边 \((s, v, w)\)，那么更新 \(dis(v) = \min\{dis(s) + w\}\)，也就是松弛一下。
对于 \(i>1\) 的情况呢？我们总能找到一个 \(x\) 满足 \(dis(x)\) 最小，且 \(x\) 不在集合 \(S\) 中。然后把 \(x\) 加入集合。然后松弛从 \(x\) 出发的边。
总结一下 dijkstra 的流程
- 找到一个 \(dis(x)\) 最小的，且不在集合 \(S\) 中的点 \(x\)。
- 把 \(x\) 加入集合 \(S\)。
- 松弛从 \(x\) 除法的边。
- 重复以上过程 \(n\) 次。
正确性证明
这样子看上去感性理解一下，是不是很正确？但是我们可以证明它。我在网上翻了翻发现其他人写的证明都好可怕∑(っ°Д°;)っ（其实是我看不懂(*/ω＼*)）。所以给一个从归纳的角度证明的方法。希望可以简短移动一点 awa
用归纳的框架来看，从 \((i - 1)\) 的局面到 \(i\) 的局面，我们干了些什么？找不在 \(S\) 中的 \(dis(x)\) 最小的 \(x\)，并且把它丢进了集合 \(S\)。用 \(x\) 松弛从它出发的边。其中 \(dis(x)\) 就是第 \(i\) 小的最短路。这样做有什么道理吗？由于我们是归纳做的，所以 \(dis(x)\) 在此时可以看成是从 \(S\) 集合里面的点，往外走一条边的最短路径长度。
很显然，从 \(s\) 到 \(x\) 的最短路一定经过源点，而且源点肯定在集合里面，也就是说最短路多少和集合 \(S\) 沾边。那么最短路就可以分成两种
- 从 \(S\) 某点出发走一条边。
- 从 \(S\) 某点出发走多条边。
由于这道题是正权图，傻子都知道肯定是第一种路径最短路小，所以我们这时候选出来的就是最短路。然后不断这样归纳下去，dijkstra 就是对的
这样证明看上去很生草，但是它是对的。
dijkstra 的一些小小局限性
- dijkstra 不能处理负权图的原因
因为这个时候走两条边和走一条边谁优就不能肯定的，也许走一个负数会更优呢？ - dijkstra 不能跑正权图最长路的原因
每一个正权图的最长路都可以看成一个负权图的最短路。dijkstra 求不了负权图最短路，相应的它也求不了正权图最长路。当然负权图最长路是可以求得。我们也可以用上面的方法来理解：从 \(S\) 走多条边肯定比从 \(S\) 走一条边要唱。
dijkstra 与 dp
这个东西我上网查了一下，但是都说的不明不白的。
想要有 dp，那一定得有这样几个前提：最优子结构性质和无后效性。我们来看看 dijkstra 有没有这几个性质。
有没有最优子结构性质呢？有。很显然，对于一条边 \((u, v, w)\)，然后更新一下 \(dis(v) = \min\{dis(u) + w\}\)。那么此时的问题就变成了求 \(dis(u)\) 的最小值了。如果 \(dis(u)\) 不是最小值相应的 \(dis(v)\) 也不是最小，最优子结构性质是有的。
无后效性呢？我们回顾一下，dijkstra 实际上是在从第 \((i - 1)\) 小的最短路推到第 \(i\) 小的最短路。虽然这张图是有环的，但是这并不会影响