摘要：对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过，边数不会超过。我会说只有三个吗适用于任何图，不管有向无向，边权正负，但是最短路必须存在。
定义
（还记得这些定义吗？如果对 图的概念 和 存储 不了解请点击链接）
路径
最短路
有向图中的最短路、无向图中的最短路
单源最短路、每对结点之间的最短路
性质
对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。
对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。
对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过 n ，边数不会超过 n−1 。
Floyd 算法
是用来求任意两个结点之间的最短路的。
复杂度比较高，但是常数小，容易实现。（我会说只有三个 for 吗？）
适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）
实现
我们定义一个数组 fk[y] ，表示只允许经过结点 1 到 k ，结点 x 到结点 y 的最短路长度。
很显然， fn[y] 就是结点 x 到结点 y 的最短路长度。
我们来考虑怎么求这个数组
f0[y] ：边权，或者 0 ，或者 +∞ （ f0[x] 什么时候应该是 +∞ ？）
fk[y] = min(fk-1[y] fk-1[k]+fk-1[y])
上面两行都显然是对的，然而这个做法空间是 O(N3) 。
但我们发现数组的第一维是没有用的，于是可以直接改成 fx = min(fx fx+fk) ，
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
f[i][j] = min(f[i][j] f[i][k] + f[k][j]);时间复杂度是 O(N3) ，空间复杂度是 O(N2) 。
应用
"给一个正权无向图，找一个最小权值和的环。"
首先这一定是一个简单环。
想一想这个环是怎么构成的。
考虑环上编号最大的结点 u。
fu-1[y] 和 (ux) (uy）共同构成了环。
在 Floyd 的过程中枚举 u，计算这个和的最小值即可。
O(n3) 。
"已知一个有向图中任意两点之间是否有连边，要求判断任意两点是否连通。"
该问题即是求 图的传递闭包 。
我们只需要按照 Floyd 的过程，逐个加入点判断一下。
只是此时的边的边权变为 1/0 ，而取 min 变成了 与 运算。
再进一步用 bitset 优化，复杂度可以到 O(n3w) 。
// std::bitset
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
if (fi) f[i] = f[i] & f[k];
Bellman-Ford 算法
一种基于松弛（relax）操作的最短路算法。
支持负权。
能找到某个结点出发到所有结点的最短路，或者报告某些最短路不存在。
在国内 OI 界，你可能听说过的“SPFA”，就是 Bellman-Ford 算法的一种实现。（优化）
实现
假设结点为 S 。
先定义 dist(u) 为 S 到 u （当前）的最短路径长度。
relax(uv) 操作指： dist(v)=min(dist(v)dist(u)+edge_len(uv)) .
relax 是从哪里来的呢？
三角形不等式： dist(v)≤dist(u)+edge_len(uv) 。
证明：反证法，如果不满足，那么可以用松弛操作来更新 dist(v) 的值。
Bellman-Ford 算法如下：
while (1) for each edge(u v) relax(u v);
当一次循环中没有松弛操作成功时停止。
每次循环是 O(m) 的，那么最多会循环多少次呢？
答案是 ∞ ！（如果有一个 S 能走到的负环就会这样）
但是此时某些结点的最短路不存在。
我们考虑最短路存在的时候。
由于一次松弛操作会使最短路的边数至少 +1 ，而最短路的边数最多为 n−1 。
所以最多执行 n−1 次松弛操作，即最多循环 n−1 次。
总时间复杂度 O(NM) 。 （对于最短路存在的图）
relax(u v) {
dist[v] = min(dist[v] dist[u] + edge_len(u v));}
for (i = 1; i <= n; i++) {
dist[i] = edge_len(S i);}
for (i = 1; i < n; i++) {
for each edge(u v) {
relax(u v);
}}
注：这里的 edge_len(uv) 表示边的权值，如果该边不存在则为 +∞ ， u=v 则为 0 。
应用
给一张有向图，问是否存在负权环。
做法很简单，跑 Bellman-Ford 算法，如果有个点被松弛成功了 n 次，那么就一定存在。
如果 n−1 次之内算法结束了，就一定不存在。
队列优化：SPFA
即 Shortest Path Faster Algorithm。
很多时候我们并不需要那么多无用的松弛操作。
很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。
那么我们用队列来维护“哪些结点可能会引起松弛操作”，就能只访问必要的边了。
q = new queue();
q.push(S);
in_queue[S] = true;
while (!q.empty()) {
u = q.pop();
in_queue[u] = false;
for each edge(u v) {
if (relax(u v) && !in_queue[v]) {
q.push(v);
in_queue[v] = true;
}
}}
虽然在大多数情况下 SPFA 跑得很快，但其最坏情况下的时间复杂度为 O(NM) ，将其卡到这个复杂度也是不难的，所以考试时要谨慎使用（在没有负权边时最好使用 Dijkstra 算法，在有负权边且题目中的图没有特殊性质时，若 SPFA 是标算的一部分，题目不应当给出 Bellman-Ford 算法无法通过的数据范围）。
SPFA 的优化之 SLF
即 Small Label First。
即在新元素加入队列时，如果队首元素权值大于新元素权值，那么就把新元素加入队首，否则依然加入队尾。
该优化在确实在一些图上有显著效果，但是如果有负权边的话，可以直接卡到指数级。
Dijkstra 算法
Dijkstra 是个人名（荷兰姓氏）。
IPA:/ˈdikstrɑ/或/ˈdɛikstrɑ/。
这种算法只适用于非负权图，但是时间复杂度非常优秀。
也是用来求单源最短路径的算法。
实现
主要思想是，将结点分成两个集合：已确定最短路长度的，未确定的。
一开始第一个集合里只有 S 。
然后重复这些操作：
对那些刚刚被加入第一个集合的结点的所有出边执行松弛操作。
从第二个集合中，选取一个最短路长度最小的结点，移到第一个集合中。
直到第二个集合为空，算法结束。
时间复杂度：只用分析集合操作， n 次 delete-min ， m 次 decrease-key 。
如果用暴力： O(n2+m)=O(n2) 。
如果用堆 O(mlogn) 。
如果用 priority_queue： O(mlogm) 。
（注：如果使用 priority_queue，无法删除某一个旧的结点，只能插入一个权值更小的编号相同结点，这样操作导致堆中元素是 O(m) 的）
如果用线段树（ZKW 线段树）： O(mlogn+n)=O(mlogn)
如果用 Fibonacci 堆： O(nlogn+m) （这就是为啥优秀了）。
等等，还没说正确性呢！
分两步证明：先证明任何时候第一个集合中的元素的 dist 一定不大于第二个集合中的。
再证明第一个集合中的元素的最短路已经确定。
第一步，一开始时成立（基础），在每一步中，加入集合的元素一定是最大值，且是另一边最小值，每次松弛操作又是加上非负数，所以仍然成立。（归纳）（利用非负权值的性质）
第二步，考虑每次加进来的结点，到他的最短路，上一步必然是第一个集合中的元素（否则他不会是第二个集合中的最小值，而且有第一步的性质），又因为第一个集合内的点已经全部松弛过了，所以最短路显然确定了。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/126246.html
摘要：由于是从顶点到的最短路径，则有。算法流程根据最短路径的最优子结构性质，提出了以最短路径长度递增，逐次生成最短路径的算法。相关文章王者编程大赛之一王者编程大赛之二蓄水池王者编程大赛之三背包王者编程大赛之四约瑟夫环 首发于 樊浩柏科学院 自如年底就会拥有 50W 间房子，大家知道每间房房子都是需要配置完才能出租给自如客的，整个房租的配置过程是很复杂的，每天都需要大量的物流师傅将家电、家具...
摘要：学习资料迪杰斯特拉计算的是单源最短路径，而弗洛伊德计算的是多源最短路径代码不能设置为，否则两个相加会溢出导致出现负权创建顶点和边 学习资料 迪杰斯特拉计算的是单源最...
摘要：推荐资料推荐学习文章代码不能设置为否则两个相加会溢出导致出现负权创建顶点和边创建图顶点数得到边的数目调用算法计算最短路径 推荐资料 推荐学习文章 代码 public...
摘要：算法系列单源最短路径算法迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。 Javascript算法系列 - 单源最短路径 - Dijkstra算法 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有...
摘要：相关操作就是判断的不等号符号改反，初始值设为负无穷副本的最短路径即为原图的最长路径。方法是同上面一样构造图，同时会添加负权重边，再将所有边取反，然后求最短路径最短路径存在则可行没有负权重环就是可行的调度。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter ...
阅读 3518·2023-04-25 20:09
阅读 3724·2022-06-28 19:00
阅读 3037·2022-06-28 19:00
阅读 3060·2022-06-28 19:00
阅读 3140·2022-06-28 19:00
阅读 2864·2022-06-28 19:00
阅读 3022·2022-06-28 19:00
阅读 2619·2022-06-28 19:00
