最短路问题，顾名思义就是要求图上的某点到另外一点的最短距离，爆搜就不用说了。
令图上点数为 \(n\)，边数为 \(m\)。
由于考虑的是最短路，那么包含负环的图就不能算了，没有最短这一说。
正权图最短路性质：任意两点间的最短路都不会经过重复的点和重复的边。
$$\texttt{Floyd}$$
优点
Floyd 可以求出两两节点间的最短路，码量较低，可以找到负权图的最短路。
缺点
时间复杂度高。
令 f[k][i][j] 表示在只经过(\(i\) 和 \(j\) 不算) \(1\sim k\) 的点的情况下 \(i\) 到 \(j\) 的最短路，显然 f[n][i][j] 就是原图上 \(i,j\) 之间最短路长度。
初始时 \(f_{0,i,j}=\begin{cases}0&i=j\\边权&i和j直接相连\\+\infty&i和j不相连 \end{cases}\)，接着三重循环枚举 \(k,i,j(1\leqslant k,i,j \leqslant n)\)，f[k][i][j] = min(f[k - 1][i][j], f[k - 1][i][k] + f[k - 1][k][j])。
优化一下，第一维对结果无影响，变为二维 f[i][j]。
时间复杂度：\(O(n^3+m)\)，空间复杂度：\(O(n^2)\)
$$\texttt{Bellman-Ford}$$
优点
可以找到负权图的单源最短路，可以判负环。
缺点
时间复杂度仍比较高。
松弛操作：对于边 \(u\xrightarrow{w} v\)，\(dis_v=\min(dis_v, dis_u+ w)\)，如果\(dis_v\) 发生了改变，就称为松弛成功。
Bellman-Ford 就是不断尝试松弛图上的边，每次循环都枚举每条边，看是否能松弛，如果所有的边都无法松弛了，那么最短路也就求完了。
在最短路存在的情况下，最多只会经过 \(n -1\) 条边，那么松弛的次数也就不会超过 \(n-1\)，当第 \(n\) 次松弛还能有松弛成功的点，就代表从原点开始能到达一个负环。
tips:如果想用 Bellman-Ford 判负环，那么最保守的方法是建立一个超级原点，向每个节点都连一条边权为 \(0\) 的边，在以它为原点做 Bellman-Ford 即可。
时间复杂度：\(O(n\times m)\)，空间复杂度：\(O(n+m)\)。
队列优化 SPFA
关于 SPFA，它死了。
很显然，只有上一轮被更新的节点所连出去的边，才有可能是可以松弛的边，可以用队列维护哪些节点可能引起松弛操作。
SPFA 大多数情况下跑到快，可最差仍然是 \(O(n\times m)\) 的。
$$\texttt{Dijkstra}$$
优点
时间复杂度低，可以求出单源或者多源最短路。
缺点
一遇到负权就寄。
主要思想：使用优先队列存储一些访问到的节点的编号和最短路长度，优先队列肯定按最短路长度从小到大。
当取出了一个队头时，如果这个节点没有被取出来过，那么就记录好答案，将它所连出去的边都进行一次松弛。
当松弛 \(u\xrightarrow{w} v\) 时，如果 \(v\) 已经被取出来过，那么就不用放入优先队列了，因为在它之前的节点的最短路长度必然是非严格小于它的，不可能更优。
时间复杂度：\(O(m\log m)\)，空间复杂度：\(O(n+m)\)。
标签：松弛,短路,Bellman,节点,复杂度,dis From： https://www.cnblogs.com/wnsyou-blog/p/17747948.html