最短路
最短路如何判断是否有负环:f[i][i]<0
,
floyd算法#
特点
- 复杂度比较高,但常数小,容易实现(只有三个for)
- 适用于任何图,不管有向无向,边权正负,但是最短路必须存在,不能有负环 代码
应用一
P6175 无向图的最小环问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
给一个正权无向图,找一个最小权值和的环。首先这一定是一个简单环。想一想这个环是怎么构成的。考虑环上编号最大的结点 。f[u-1][x][y]
和 (y,u)
,(u,x)
共同构成了环。在 Floyd 的过程中枚举u
,计算这个和的最小值即可,时间复杂度为O(n^3)
应用二 已知一个有向图中任意两点之间是否有连边,要求判断任意两点是否连通。
该问题即是求 图的传递闭包。 我们只需要按照 Floyd
的过程,逐个加入点判断一下。只是此时的边的边权变为 1/0
,而取 min
变成了 或 运算。再进一步用 bitset
优化,复杂度可以到 O(n^3/w)
。
Dijkstra算法#
不适用 有负数权值的边
暴力 不使用任何数据结构进行维护,每次 2 操作执行完毕后,直接在 T 集合中暴力寻找最短路长度最小的结点。2 操作总时间复杂度为 O(m)
,1 操作总时间复杂度为O(n^2)
,全过程的时间复杂度为 O(n^2 + m) = O(n^2)
。
优先队列
- 二叉堆:每成功松弛一条边
(u,v)
,就将v插入二叉堆中(如果 v
已经在二叉堆中,直接修改相应元素的权值即可),1
操作直接取堆顶结点即可。共计O(m)
次二叉堆上的插入(修改)操作,O(n)
次删除堆顶操作,而插入(修改)和删除的时间复杂度均为 O(logn)
,时间复杂度为 O((n+m)logn) = O(mlogn)
。 - 优先队列:和二叉堆类似,但使用优先队列时,如果同一个点的最短路被更新多次,因为先前更新时插入的元素不能被删除,也不能被修改,只能留在优先队列中,故优先队列内的元素个数是
O(m)
的,时间复杂度为 O(mlogm)
。
Bellman–Ford 算法#
Bellman–Ford
算法是一种基于松弛(relax)
操作的最短路算法,可以求出有负权的图的最短路,并可以对最短路不存在的情况进行判断。
[[判断是否有负环#处理图中存在环的最短路径算法|Bellman–Ford 算法如何判断是否有负环]] 需要注意的是,以s点为源点跑Bellman–Ford
算法时,如果没有给出存在负环的结果,只能说明从s
点出发不能抵达一个负环,而不能说明图上不存在负环。
因此如果需要判断整个图上是否存在负环,最严谨的做法是建立一个超级源点,向图上每个节点连一条权值为 0
的边,然后以超级源点为起点执行Bellman–Ford
算法。
过程 Bellman–Ford
算法所做的,就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环,就对图上所有的边都尝试进行一次松弛操作,当一次循环中没有成功的松弛操作时,算法停止。
每次循环是 O(m)
的,那么最多会循环多少次呢? 在最短路存在的情况下,由于一次松弛操作会使最短路的边数至少 +1
,而最短路的边数最多为 n-1
,因此整个算法最多执行 n-1
轮松弛操作。故总时间复杂度为 O(nm)
。
代码
队列优化:SPFA
很多时候我们并不需要那么多无用的松弛操作。
很显然,只有上一次被松弛的结点,所连接的边,才有可能引起下一次的松弛操作。
那么我们用队列来维护「哪些结点可能会引起松弛操作」,就能只访问必要的边了。
SPFA 也可以用于判断 s
点是否能抵达一个负环,只需记录最短路经过了多少条边,当经过了至少 n
条边时,说明 s
点可以抵达一个负环。