浅浅证明一下Dijkstra
一直都在写dij，证明一下正确性。
下面的证明在有向图中。
首先，对于一个点u，假设它的某一条最短路径中，从源点出发，一直到u，将沿路的节点记录下来，u的前一个节点是x（可以认为是u的前驱x）。
那么一定有dist[u]=dist[x]+w[x,u]。
因为一定是从源点走到x，再从x走到u，每一种走法中，x到u的权值是固定的，所以可以删去它再考虑最小值。
也就是说，如果一个点x是点u的最短路径的前驱，那么一定是从dist[x]转移给dist[u]的。
最短路径前驱的的集合，是能到达u的点集的子集。
那么那些能到u的点，才是前驱呢？
因为是最短路，当然是dist[x]+w[x,u]最小的那些点x啦！
所以我们可以让能到达u的所有x，都更新一下dist[u]。
那么问题来了，我们要用dist[x]去更新dist[u]，首先得保证dist[x]被求出来了呀。
这就需要证明一下dij中的一个灵魂结论：如果一个点是当前未确定最短路的点集中，已知最短路长度最小的，那么它的最短路长度就是已知最短路长度。
假设在该点之前确认的最短路长度都是正确的。
反证法，假设该点的最终最短路长度 \(d\) 小于 已知最短路长度 \(d_0\)。
即假设 \(d < d_0\)
假设它的一个可能的前驱是x；
- 如果x属于未确定的点集（与u不相等）
因为
$ dist[x] \ge dist[u] $
$ w[x, u] \ge 0 $
所以 \(dist[x] + w[x, u] \ge dist[u]\) 即 \(d \ge d_0\) 与假设矛盾。
- 如果x属于最短路已经确定的点集
因为最短路已经确定的点集中的x已经去更新了以x为前驱的所有路径，自然包括了u的这一条，所以此时 \(d_0 = d\)，与假设矛盾。
初始时，源点到自己的距离为0，为最小值。
综上，如果一个点是当前未确定最短路的点集中，已知最短路长度最小的，那么它的最短路长度就是已知最短路长度。
所以是正确的捏。