图论随手记 - 最短路

顺序有点乱，后续会排一下，然后分板块整理

All

Dijkstra = 贪心 + DP 时间复杂度： \text{O}(m \log m)
证：在 Dijkstra 算法过程中，每次找出 dis 最小的没有被确定最短路的点，它的 dis 一定是源点到它的最短路。

注意：正难则反 \to 反证法

证明： 设 S 集合表示最短路已经确定的点， T 集合表示最短路还没有确定的点。

即证： T 集合中 dis 最小的元素可以直接加入到 S 集合中。

所以 dis 中储存的数值，为从源点到 u，只经过 S 集合中的点所得到的最短路。

反证：

设当前 T 集合中 dis 最小的元素为 u，且 dis_{u} 不为源点到 u 的最短路。

如果有一条更短的最短路，那么，这两条路径中至少要有一个点不同。

设最早不同的点为，v_1 和 v_2，v_2 为更短最短路中的一个点， v_1 为当前路径中的一个点。

当且仅当，v_2 在 T 集合中，才会没有被更新到。

又因为，dijkstra 只能处理非负权图。（这里也可以说明为什么 dijkstra 只能处理非负权图）

所以， dis_{v_2} 只能小于 dis_u 才能更新到 u。（如果有负权，这里会出问题）

发现，这与 dis_u 为 T 集合中最小的元素矛盾。

所以，不存在 v_2。

得证
有的时候，dijkstra 堆优化是负优化。

Eg. m = n ^ 2

时间复杂度为： O(n^2 \log n^2)，不如暴力的 O(n ^ 2)。

有关 Floyd 的题目主要需要考虑 Floyd 中能提供的信息，而不能只看到 Floyd 提供的任意两点之间的最短路或者是传递闭包。（TODO： Floyd 深度理解【坑 ++】）
Floyd 跑3遍，任意循环顺序都可以求出全源最短路。
证明： Floyd 的 k, i, j 枚举顺序为什么可行？

回归 Floyd 的本初，原本为 DP，状态为 dp[k][i][j] ：仅前 k 个点， i \to j 的最短路。
dp[k][i][j] = \min(dp[k][i][j], dp[k - 1][i][k] + dp[k - 1][k][j])
此时,显然可行。

怎么滚动掉第一维的？

在 DP 的角度上看，这样的滚动是会使用到更新过的值，而非使用上一轮的数据。

但是，这里 dp_{k, i, k} 由于其中不经过 k，所以等价于 dp_{k - 1,i,k}，覆盖了也没关系，所以只要原先状态与覆盖状态意义相同，则同样可以使用滚动数组。
Floyd 的中间过程，也有一定意义。
Q: Floyd 可以用来判断负环吗？

A: 可以，跑两次 Floyd，在负环上的点则 dis 一直在减少。