简单最短路径算法
前言
图的最短路径算法主要包括:
- 有向无权图的单源最短路径
- 宽度优先搜索算法(bfs)
- 有向非负权图的单源最短路径
- 迪杰斯特拉算法(Dijkstra)
- 有向有权图的单源最短路径
- 贝尔曼福特算法(Bellman-Ford)
- 最短路径快速算法(SPFA)
- 有向有权图的多源最短路径
- 弗洛伊德算法(Floyd)
- 负环
- 约翰逊算法(Johnson)
- 有向非负权图的单源k短路径:
- 迪杰斯特拉算法(Dijkstra)
- 有向非负权图的单源汇k短路径:
- 启发式搜索算法(A*)
事实上k短路径可以用可持久化可并堆来做,但是我不会。
- 启发式搜索算法(A*)
- 有向无环图的单源最短路径
- 拓扑排序+动态规划
关于简单路径的问题:
事实上图上任意一条长度不为 − ∞ -\infty −∞的最短路径一定是简单路径,并且任意一条长度不为 + ∞ +\infty +∞的最长路径也一定是简单路径。显然。
我们把所有边的边权取反,这样原来的最长路径就成为了最短路径,原来的最短路就成为了现在的最长路。
约定
- 对于无权图 G G G,我们认为它相当于边权全为 1 1 1的带权图。
- 负环指的是环上所有边的边权和为负数的环,正环同理。
- 本文所说的最短路径,并不要求路径上没有重复节点,即路径上可能存在环。
事实上最短路径上的环一定是负环或零环,零环可以舍去,因此如果图中不存在负环,则我们认为最短路径一定是简单路径 - 我们用 d i s u , v dis_{u,v} disu,v表示图中从 u u u到 v v v的最短路,记作 u u u到 v v v的距离
- 单源最短路径指的是,起点为固定的一个点 S S S,终点为图中任意点的所有最短路径。
即单源最短路径算法要求出: d i s S , u ∈ V dis_{S,u\in V} disS,u∈V
宽度优先搜索算法(bfs)
bfs算法求出有向无权图上的单源最短路径。
bfs算法的过程是这样的:
- 初始, S S S与自身的距离为 0 0 0
- 标记所有 S S S的临接点,它们与 S S S的距离为 1 1 1
- 标记所有 f u = 1 f_u=1 fu=1的点的临接点中未被标记的点,它们与 S S S的距离为 2 2 2
- 标记所有 f u = 2 f_u=2 fu=2的点的临接点中未被标记的点,它们与 S S S的距离为 3 3 3
- 标记所有 f u = 3 f_u=3 fu=3的点的临接点中未被标记的点,它们与 S S S的距离为 4 4 4
- …
- 以此类推,直到所有点都被标记。
很容易使用归纳的方法证明bfs算法的正确性:
假设目前标记了所有 d i s S , u ≤ k dis_{S,u}\leq k disS,u≤k的点,并正确计算了其距离,显然所有 d i s S , u = k + 1 dis_{S,u}=k+1 disS,u=k+1的点都会在下一轮当中被扩展。
可以使用队列来维护这个过程,具体来说是:
- 首先把 S S S加入队列,标记 S S S
- 设目前队列的队头为 u u u,把队头的所有未被标记的临接点 v v v的距离更新, f v = f u + 1 f_v=f_u+1 fv=fu+1,然后标记这些点,把它们入队
- 弹出队头
- 重复这个入队出队的过程直到队列为空
时间复杂度 O ( n + m ) O(n+m) O(n+m),其中 n n n为图的点数, m m m为边数。
迪杰斯特拉算法(Dijkstra)
松弛
在一般的求解单源最短路的过程中,我们需要维护 d u d_u du表示当前已知的从 S S S到 u u u的最短路径长度,或称 d u d_u du为从 S S S到 u u u的最短路径长度的上界,即最短路径估计。初始 d S = 0 , d u ∉ S = + ∞ d_S=0,d_{u\not\in S}=+\infty dS=0,du∈S=+∞
对于图中一条从 u u u到 v v v的有向边,其边权为 w w w,我们知道在最终的最短路上一定满足 d i s u + w ≥ d i s v dis_u+w\geq dis_v disu+w≥disv,因此如果当前的 d u + w < d v d_u+w<d_v du+w<dv,那我们可以从 u u u走这一条边来作为当前到达 v v v的最短路,说明 v v v的最短路径上界为 d u + w d_u+w du+w而不是 d v d_v dv,因此执行 d v ← d u + w d_v\leftarrow d_u+w dv←du+w。
因此我们选出一条边 ( u , v ) (u,v) (u,v),尝试用 d u d_u du来更新 d v d_v dv的过程叫做松弛,如果成功更新了 d v d_v dv,那称为松弛成功,否则称为松弛失败。
松弛的过程:
if(d[u]+w<d[v])d[v]=d[u]+w;
迪杰斯特拉算法
迪杰斯特拉算法是一种求解非负权图的单源最短路径的算法。
迪杰斯特拉算法的过程是这样的:
- 初始所有点都未被标记
- 选出目前 d d d最小的未被标记的点,设为 u u u
- 标记 u u u
- 用 u u u的所有出边进行松弛操作
- 直到所有点都被标记,此时 d u = d i s S , u d_u=dis_{S,u} du=disS,u
证明
引理1
归纳可以证明由于边权非负,如果把被标记的点排成一个序列,则它们的 d d d一定非严格递增。
引理2
u u u是从 S S S到 v v v的其中一条最短路上 v v v的前驱的充要条件是: d i s S , u + w = d i s S , v dis_{S,u}+w=dis_{S,v} disS,u+w=disS,v
w w w表示最短路上从 u u u到 v v v的边的边权
引理2显然。
引理3
假设 u u u是从 S S S到 v v v的其中一条最短路上 v v v的前驱,若对边 ( u , v ) (u,v) (u,v)进行松弛时, d u = d i s S , u d_u=dis_{S,u} du=disS,u,则松弛后 d v = d i s S , v d_v=dis_{S,v} dv=disS,v
若松弛成功,则 d v = d u + w = d i s S , u + w = d i s S , v d_v=d_u+w=dis_{S,u}+w=dis_{S,v} dv=du+w=disS,u+w=disS,v
若松弛失败,则 d v d_v dv本来就等于 d i s S , v dis_{S,v} disS,v
引理4
d i s u , x + d i s x , v ≥ d i s u , v dis_{u,x}+dis_{x,v}\geq dis_{u,v} disu,x+disx,v≥disu,v
若小于,则先沿着 u , x u,x u,x的最短路走到 x x x,再沿着 x , v x,v x,v的最短路走到 v v v,会得到比 d i s u , v dis_{u,v} disu,v更短的最短路,与 d i s u , v dis_{u,v} disu,v的定义矛盾
引理5
若从 u u u到 v v v的某条最短路经过了 x x x,则 d i s u , x + d i s x , v = d i s u , v dis_{u,x}+dis_{x,v}=dis_{u,v} disu,x+disx,v=disu,v
根据引理4,我们知道 d i s u , x + d i s x , v ≥ d i s u , v dis_{u,x}+dis_{x,v}\geq dis_{u,v} disu,x+disx,v≥disu,v,而显然 d i s u , x + d i s x , v > d i s u , v dis_{u,x}+dis_{x,v}>dis_{u,v} disu,x+disx,v>disu,v的话,不可能存在一条经过 x x x的最短路。
迪杰斯特拉算法的正确性
归纳假设之前的所有被标记的点被标记时,都满足其最短路径估计( d d d)等于其最短路径长度( d i s dis dis):
设下一次被选出的点是 v v v,则我们可以证明选出它时, d v = d i s S , v d_v=dis_{S,v} dv=disS,v:
找到其中一条由 S S S到 v v v的最短路上 v v v的前驱 u u u
- 若 w > 0 w>0 w>0
则 u u u一定被标记,说明 d u = d i s S , u d_u=dis_{S,u} du=disS,u松弛了 v v v,根据引理3证毕。 - 否则 w = 0 w=0 w=0
- 若至少存在一个前驱 u u u满足从 u u u到 v v v在 S S S到 v v v最短路上的边不为 0 0 0:
则是上面的情况,证毕。 - 否则所有的 u u u到 v v v在最短路上的边均为 0 0 0:
-
如果存在至少一个 u u u被标记:
根据引理3证毕。 -
不存在任何一个 u u u被标记:
说明 v v v尚未被任意一个最短路上的前驱更新,根据引理3可知, d v > d i s S , v d_v>dis_{S,v} dv>disS,v
那么一定可以找到一个点 x x x,使得:- x x x被标记
- x x x在某条从 S S S到 v v v的最短简单路径上
- x x x在此条最短路径上的后继 y y y未被标记。
我们一定能选出一个这样的点,因为满足限制 1 , 2 1,2 1,2的点是一定有的,而如果后继 y y y不满足未被标记,说明 y y y满足限制 1 , 2 1,2 1,2,则我们可以令 x ← y x\leftarrow y x←y,由于简单路径的长度至多为 n n n,因此最多跳约 n n n次就会找到一个合法的点 x x x:
因此我们知道 d x = d i s S , x d_x=dis_{S,x} dx=disS,x,那根据引理3我们就知道 d y = d i s S , y d_y=dis_{S,y} dy=disS,y,这样我们就会知道 d y = d i s S , y ≤ d i s S , v < d v d_y=dis_{S,y}\leq dis_{S,v}<d_v dy=disS,y≤disS,v<dv,即 d y < d v d_y<d_v dy<dv,但是 y y y又未被标记,不满足引理 1 1 1,矛盾。
-
- 若至少存在一个前驱 u u u满足从 u u u到 v v v在 S S S到 v v v最短路上的边不为 0 0 0:
证毕。
实现
#include<iostream>
#include<vector>
#include<queue>
#include<vector>
#include<functional>
#include<map>
using namespace std;
const int N=1e5;
vector<pair<int,int>>a[N+5];
int d[N+5];
bool vis[N+5];
void Dijk(int s) {priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;for(auto&i:d) i=1e9;q.push({0,s});d[s]=0;while(!q.empty()){int u=q.top().second;q.pop();if(vis[u]) continue;vis[u]=true;for(auto&i:a[u]) {int v=i.second,w=i.first;if(d[v]>d[u]+w) d[v]=d[u]+w,q.push({d[v],v});}}
}
int main(){int n,m,s;cin>>n>>m>>s;for(int i=1,u,v,w;i<=m;i++){cin>>u>>v>>w;a[u].push_back({w,v});}Dijk(s);for(int i=1;i<=n;i++) cout<<d[i]<<' ';
}
迪杰斯特拉算法事实上是一种优先队列bfs算法。其和朴素bfs算法的正确性保证是一致的:
- 按照距离 S S S从近到远的点为前驱依次松弛,必定得到最短路。
- 由于边权非负,当前距离 d u d_u du最小的未被标记的点一定是未被标记点中 d i s S , u dis_{S,u} disS,u最小的点
因此我们可以用优先队列快速求出 d i s S , u dis_{S,u} disS,u最小的未被标记点,这样可以保证每个点的出边至多只会松弛一次,这样就有了时间复杂度保证。
如果第二点不成立,那么我们无法找到目前 d i s S , u dis_{S,u} disS,u最小的未被标记点,我们就不能保证按照标记顺序松弛一定得到最短路,为了确保正确性,就不能保证被标记的点的出边不会再次用于松弛,因此时间复杂度分析就不成立了,也就得到了SPFA算法。
贝尔曼-福特算法(Bellman-Ford)
贝尔曼福特算法和最短路径快速算法(SPFA)都是一种用来求解有权有向图单源最短路径的算法。
由于这两种算法允许负权边的存在,因此应用范围更广一些,但是它们的时间复杂度较迪杰斯特拉也更劣。
负环
若有向图 G G G中只存在非负权边,则显然 S S S到任意可达点的最短路径长度为非负实数,是一个有限值。
但是如果存在这样的图:
则从 S S S到 T T T的路径上存在一个负环,那此时最短路径不再是简单路径,我们可以绕着负环不断行走,可以使得最短路径的权值变得越来越小,因此从 S S S到 T T T的最短路径长度为 − ∞ -\infty −∞。
最短路径存在定理
从 u u u到 v v v存在有限长度的最短路径的充要条件是, u u u可达 v v v且 u u u到 v v v的任何一条路径上不能存在负环。
证明:
必要性很显然,只证明充分性。
“ u u u到 v v v的任一路径均无负环是 u u u到可达点 v v v有最短路的充分条件。”
考虑其逆否命题:
“ u u u到可达点 v v v无有限长度的最短路,是 u u u到 v v v的至少一条路径上有负环的充分条件。”
假设 u u u到 v v v没有有限长度的最短路,说明 d i s u , v = − ∞ dis_{u,v}=-\infty disu,v=−∞,由于有限条边构成的路径一定是有限长度,因此 u u u到 v v v的最短路经过的点数为 + ∞ +\infty +∞。
把最短路经过的点的编号顺次排列为 a a a,然后我们可以删掉 a a a中所有零环,这样 a a a仍然是最短路序列。
由于只有 n n n个点,由于鸽巢原理,序列的前 n + 1 n+1 n+1项中至少有两个位置是相同的,设为 a x , a y a_x,a_y ax,ay,则必然满足从 x x x沿着对应的路径走到 y y y,经过的边权和一定 < 0 <0 <0,说明有负环。
逆否命题成立,说明原命题成立。证毕。
(也可以直接证,但是我当时没想到,不想再改步骤了。)
这说明:有向图 G G G上任意有序点对要么不可达,要么存在有限长度的最短路径的充要条件是,图 G G G中没有负环。
最短路DAG与最短路径树
方便起见假设以 S S S为起点可以到达任何点。
以 S S S为起点,对于有向边 ( u , v ) (u,v) (u,v),如果满足 d i s S , u + w = d i s S , v dis_{S,u}+w=dis_{S,v} disS,u+w=disS,v,就在新图上给 ( u , v ) (u,v) (u,v)连有向边,这样得到一张新图。
如果原图从 S S S到任一点的路径上没有零环、负环,则显然这张图是一个DAG(有向无环图)。
我们对这张图求出一个以 S S S为根的外向生成树,称为最短路径树。
这个生成树一定能求出来的,因为新图上只有 S S S点可能入度为 0 0 0,我们可以通过归纳来得到这个结论。(具体来说,我们考虑往图上添加一个入度不为0的点,或添加一个有向边,结论仍然成立)
那么根据引理3和归纳法,我们可以知道,如果从 S S S到任意点没有负环,对最短路径树进行宽度优先遍历,在遍历到节点 u u u的同时,用它与它父亲连接的那条边对 u u u在原图上进行松弛操作,会得到 d u = d i s S , u d_u=dis_{S,u} du=disS,u。
贝尔曼-福特算法
对图中的每一条边都进行一遍松弛的过程(松弛顺序无所谓),我们称为进行了一次全局松弛。
贝尔曼福特算法证明:从 S S S开始到任意可达点的无负环的充要条件是,对图进行 n − 1 n-1 n−1轮全局松弛后 d u = d i s S , u d_u=dis_{S,u} du=disS,u。
贝尔曼福特算法同时也给出了 S S S到任意可达点有至少一条路径经过负环的充要条件,即再进行第 n n n轮全局松弛时,有至少一个点仍被松弛。
证明:
我们假设从 S S S到 u u u的经过的点数最少的最短路径的点数为 k + 1 k+1 k+1,我们可以归纳证明,点 u u u最后一次被松弛是在第 k k k轮全局松弛时,并此时 d i s S , u = d u dis_{S,u}=d_u disS,u=du。因此证完。
显然贝尔曼福特算法的复杂度为 O ( n m ) O(nm) O(nm)
贝尔曼-福特算法的实现:
- 先重复进行 n − 1 n-1 n−1轮全局松弛
- 再进行一轮全局松弛,期间观察是否有点会被再次松弛,如果有,那么报告有负环。
贝尔曼-福特算法理论上码量比SPFA要小,但是我个人感觉SPFA好写,由于二者最劣复杂度一样,因此我们学习SPFA。
最短路径快速算法(SPFA)
最短路径快速算法的英文是“Shortest Path Faster Algorithm”,从这可以看出它在随机图下表现相当优秀,经过分析可以知道它在随机图下表现的复杂度大概为 O ( m + n log 2 n ) O(m+n\log^2n) O(m+nlog2n),但是它的最劣复杂度仍为 O ( n m ) O(nm) O(nm)。
SPFA算法是贝尔曼福特算法的队列优化版本,其核心思想在于,只有前驱在第 k − 1 k-1 k−1轮全局松弛中被松弛的节点,才有可能在第 k k k轮松弛中被松弛,因此我们可以用队列来模拟这个过程,具体来说是:
- 初始把 S S S入队
- 取出队头 u u u
- 如果 u u u已经入队 n n n次,那么报告有负环。
- 用队头 u u u去松弛它的所有后继,并把所有松弛成功的不在队列内的后继入队。
- 弹出队头
- 重复这个过程直到队列为空
注意有负环一定是入队 n n n次,而不是松弛 n n n次。因为入队 n n n次表示目前进行的是第 n n n轮全局松弛,但是松弛 n n n次并不一定。
正确性证明:
如果把所有松弛成功的点直接入队,那么这个算法的正确性是显然的。
现在考虑为什么如果一个点 v v v在队列内,那么就不需要重复入队:
假设 v v v被 u u u松弛成功,此时实际上是第 k k k轮全局松弛,即将入队之时发现它已经在队列内,此时有两种可能性:
- v v v是在第 k k k轮全局松弛时入队的:
因此 v v v在队列表示,第 k + 1 k+1 k+1轮全局松弛需要用 v v v来松弛,因此显然 v v v不需要再入队一次。 - v v v是在第 k − 1 k-1 k−1轮全局松弛时入队的:
我们考虑按照队序顺次执行第 k k k轮松弛,把最后一个成功松弛 v v v的点设为 x x x。- 如果 x x x队序在 v v v之后:
那么说明 v v v已经再次入队,并表示第 k + 1 k+1 k+1轮松弛需要用到 v v v来更新,此时显然正确。 - 否则 x x x队序在 v v v之前:
那么由于把 v v v在第 k + 1 k+1 k+1轮入队的唯一作用就是,计算在第 k k k轮中对 v v v松弛造成的影响。而这个影响可以直接由 v v v这个位置计算,因此是可以的。
- 如果 x x x队序在 v v v之后:
QED.
实现
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int N=1e5;
vector<pair<int,int>> a[N+5];
long long d[N+5];
bool vis[N+5];
int cnt[N+5];
int n,m,s;
void Dijk(int s) {for(auto&i:d) i=1e18;d[s]=0;queue<int>q;q.push(s);while(!q.empty()) {int u=q.front();q.pop();vis[u]=false;if(++cnt[u]>=n) throw;有负环for(auto&i:a[u]) {int v=i.second;long long w=i.first;if(d[v]>d[u]+w) {d[v]=d[u]+w;if(!vis[v])q.push(v);}}}
}
int main() {cin>>n>>m>>s;for(int i=1,u,v,w; i<=m; i++) {cin>>u>>v>>w;a[u].push_back({w,v});}Dijk(s);for(int i=1; i<=n; i++) cout<<min(d[i],(1ll<<31)-1)<<' ';
}
SPFA算法有很多的优化,例如dfs-SPFA就是用栈来模拟SPFA的过程,这种做法在判断负环上似乎有着不错的表现,但是最劣情况下仍然是指数级别的。除此以外,堆优化SPFA/SLF/LLL的优化在负权图上都有可能被卡成指数级算法。
弗洛伊德算法(Floyd)
弗洛伊德算法能够以 O ( n 3 ) O(n^3) O(n3)的复杂度求出有向有权图中任意两点之间的最短路径长度,并以 O ( n 3 ) O(n^3) O(n3)的复杂度判断负环,看起来用处不大,但是有的时候还是有用的。
弗洛伊德算法实质上是一种动态规划算法。
首先设 f k , i , j f_{k,i,j} fk,i,j表示起点为 i i i,终点为 j j j的所有路径中,不包括起点和终点,经过的点编号均在 [ 1 , k ] [1,k] [1,k]之间的最短路。
初值:
- f k , i , i = 0 f_{k,i,i}=0 fk,i,i=0
- 如果 i i i到 j j j有边, f 0 , i , j = w i , j f_{0,i,j}=w_{i,j} f0,i,j=wi,j,如果有重边,选择边权最小的一条边。
- 其余 f k , i , j = + ∞ f_{k,i,j}=+\infty fk,i,j=+∞
转移:
f k , i , j = min { f k − 1 , i , j , f k − 1 , i , k + f k − 1 , k , j } f_{k,i,j}=\min\{f_{k-1,i,j},f_{k-1,i,k}+f_{k-1,k,j}\} fk,i,j=min{fk−1,i,j,fk−1,i,k+fk−1,k,j}
注意到 f k − 1 , i , k = f k , i , k , f k − 1 , k , j = f k , k , j f_{k-1,i,k}=f_{k,i,k},f_{k-1,k,j}=f_{k,k,j} fk−1,i,k=fk,i,k,fk−1,k,j=fk,k,j,并且有一个转移是从 f k − 1 , i , j → f k , i , j f_{k-1,i,j}\rightarrow f_{k,i,j} fk−1,i,j→fk,i,j,因此可把贡献写成这个形式:
k ∈ [ 1 , n ] : f i , j min ← f i , k + f k , j k\in[1,n]:f_{i,j}\min\leftarrow f_{i,k}+f_{k,j} k∈[1,n]:fi,jmin←fi,k+fk,j
时间复杂度 O ( n 3 ) O(n^3) O(n3)
因为dp结束后, f i , j f_{i,j} fi,j的意义是,从 i i i到 j j j经过的边数不超过 n n n的最短路径,所以图上存在负环的充要条件是,dp结束后存在 f i , i < 0 f_{i,i}<0 fi,i<0。
注意,必须要先枚举 k k k,如果不先枚举 k k k是一定会错的。
负环
我们讨论几个问题:
- 负环判断问题
- 无穷最短路径问题
- 负环构造问题
- 负环计数问题
负环判断问题
以 S S S为起点进行SPFA,容易判断是否存在 S S S可达的负环。很多情况下我们更想知道这张图中是否存在负环,这时候我们需要建立虚拟源点,让源点向着每个点连接一个长度为 0 0 0的有向边,这时候在以源点为起点跑SPFA,就可以判断图中是否存在负环。
尤其需要注意,由于我们建立的虚拟源点,因此事实上图中一共有 n + 1 n+1 n+1个点,因此入队次数并不是为 n n n即说明有负环,而是入队次数等于 n + 1 n+1 n+1说明有负环。
因此实际跑SPFA的过程中,我们可以多跑几层bfs,例如统一当入队次数为 n + 2 n+2 n+2时再报告负环。
无穷最短路径问题
无穷最短路径问题指的是,对于以 S S S为起点,对 S S S距离其有限长度的所有点求出最短路,并求出 S S S到哪些点的最短路为 − ∞ -\infty −∞。
事实上SPFA可以部分处理图中有负环的情况:
假设红色为负环,虽然负环可达的点的最短路无法求出,但是由于中止算法时已经是在模拟第 n n n轮全局松弛,剩余部分的最短路在中止算法时是已经求出了的。
如果我们能够求出负环上至少一点的位置,那么我们就可以通过缩点在DAG上dp的方法来得知,哪些点是负环可达的点。
负环位置定理
事实上有以下事实:
负环所在的强连通分量的点没有有限长度的最短路。
负环可达的强连通分量的点没有有限长度的最短路。
这都是显然的。
为了方便,我们称有负环存在的连通分量为负连通分量,那么我们就会知道:
不存在两个强负连通分量互相可达。
这也是显然的,因为不存在两个强连通分量互相可达。
如果一个强负连通分量不可以被其他任何强负连通分量达到,那么称这个强负连通分量为关键强负连通分量。具体来说就是“处于可达关系最上层的强负连通分量”,关键强负连通分量意味着它可达的所有点都无法求出有限长度的最短路:
用红色表示负环,这张图中有两个关键强负连通分量,用绿色圈起来了。
负环位置定理:
每个关键强负连通分量上至少有一点在SPFA算法中入队 n n n次(或在贝尔曼福特算法的第 n n n轮全局松弛中仍被松弛成功。)
换句话说:
强连通分量 X X X是关键强负连通分量,是 X X X上至少有一点在SPFA算法中入队 n n n次的充分条件。(注意不是必要条件,因为入队 n n n次的点也可能是负环可达的点。)
这个定理显然成立。
如果要找到每个 S S S可达的关键强负连通分量,那么我们就不能在发现有点入队次数为 n n n时立即break,而是将入队次数为 n n n的点标记下来,然后等到发现有点入队次数为 n + 1 n+1 n+1时,在break。
时间复杂度 O ( n m ) O(nm) O(nm)
负环构造问题
在一张图中,可能存在的负环数量是指数级的,因此想要找到一个复杂度非指数级的构造所有负环的算法是不可能的。
但是我们可以找到图中的某个负环。
非简单负环一定是由负环+负环/正环/零环构成,因此存在非简单负环的充要条件是存在简单负环,因此我们只需要找简单负环。
假如说 v v v最后一次是被点 u u u松弛,那么我们认为当前最短路径树上 u u u是 v v v的父亲,我们可以通过使用LCT维护当前最短路径树之类的办法来求出图中的一个简单负环。
因为求出一个负环之后最短路径树就不复存在了,因此不太能做。
如果我们想要求出图中多个负环,那么注意到简单负环一定是最小环,我们可以模仿求最小环的方法求出负环。
例如使用弗洛伊德算法以 O ( n 3 ) O(n^3) O(n3)的时间复杂度求出图中的若干个简单负环。
除此之外还有一些复杂度高达 O ( n m 2 ) O(nm^2) O(nm2)之类的奇怪办法求负环,大概的思想是:
- 枚举一条边 ( u , v ) (u,v) (u,v),假设它在负环上
- 在去除这条边的图上跑SPFA求出 v v v到 u u u的最短路
- 如果发现 v v v到 u u u有负环,那么说明在没有这条边的情况下图仍有负环,永久删去这条边,在新图上递归找负环
- 否则我们就找到了包含这条边的最小环,检验一下是否为负环,如果为负环那就找到了
但是这个东西的期望时间复杂度为 O ( n m log 2 n ) O(nm\log^2n) O(nmlog2n)
有没有其他做法呢?
- 如果找到有限个负环,并且实际上负环足够多的话,可以直接维护最短路径树来做。
- 如果负环不够多呢?
说明负环应该不太多,可以试试直接搜- 不知道
负环计数问题
负环计数问题明显是强于环计数问题的,环计数问题没有公认的多项式做法,所以负环计数问题也没有。
约翰逊算法
约翰逊算法以 O ( n m + k m log m ) O(nm+km\log m) O(nm+kmlogm)的复杂度求出有权有向图中 k k k个起点的单源最短路径,它的时间复杂度事实上是一遍SPFA加 k k k遍迪杰斯特拉。
为了方便我们假设图中没有负环,如果图中有负环,那么关键强负连通分量可达的点可以直接删去。这是一个无穷最短路径问题。
约翰逊算法的关键在于重定边权,使得图中没有负权边,因此可以跑迪杰斯特拉算法。
假设我们以 S S S为超级源点求出单源最短路径 d d d,那么对于每条边都会有 ( u , v ) (u,v) (u,v):
d u + w ≥ d v d_u+w\geq d_v du+w≥dv
也即: d u − d v + w ≥ 0 d_u-d_v+w\geq 0 du−dv+w≥0
所以我们令这条边的新边权为 w ′ = d u − d v + w w'=d_u-d_v+w w′=du−dv+w
容易发现这样得到的新图上从 S S S到 T T T的路径的长度实际为: d S − d u + 原图上对应路径的长度 d_S-d_u+原图上对应路径的长度 dS−du+原图上对应路径的长度
并且这条边的边权始终非负,因此可以对每个起点都跑迪杰斯特拉。
迪杰斯特拉算法求单源k短路径
显然在堆优化迪杰斯特拉算法节点 u u u第 k k k次出队时,对应的是从 S S S到 u u u的第 k k k短路径(非严格),因此我们可以使用堆优化迪杰斯特拉算法来求出第 k k k短路,其时间复杂度为 m k log m k mk\log {mk} mklogmk。
其只能应用于有向非负权图。想要将其应用于有向有权图上,一种简单的方法是,使用约翰逊方法重定边权。
如果我们要求出严格次短路,那我们就要找到第一次,出队时对应的距离严格大于最短路径,的时间。
启发式搜索算法(A*)
启发式搜索算法通常由于快速求出从源点 S S S到汇点 T T T的第 k k k短路,其关键在于,把迪杰斯特拉算法中小顶堆比较的权值由 d u d_u du改为 d u + d i s u , T d_u+dis_{u,T} du+disu,T,也就是加入估价函数值的优先队列bfs。
由于A*算法的正确性分析,这个算法是一定对的。
该算法平常表现不错,但是其最劣复杂度仍为 O ( m k log m ) O(mk\log m) O(mklogm),也就是会被卡。
有向无环图的单源最短路径
有向无环图的单源最短路径可以DAG上dp得到。
具体来说,设 f u f_u fu表示 S S S到 u u u的最短路径,则 f v = min u → v { f u + w } f_v=\underset{u\rightarrow v}\min\{f_u+w\} fv=u→vmin{fu+w}
初始 f S = 0 , f u ≠ S = + ∞ f_S=0,f_{u\not=S}=+\infty fS=0,fu=S=+∞
时间复杂度 O ( n + m ) O(n+m) O(n+m)
可以求出拓扑序之后dp,或者进行记忆化搜索。
后记
于是皆大欢喜。
相关文章:
简单最短路径算法
前言 图的最短路径算法主要包括: 有向无权图的单源最短路径 宽度优先搜索算法(bfs) 有向非负权图的单源最短路径 迪杰斯特拉算法(Dijkstra) 有向有权图的单源最短路径 贝尔曼福特算法(Bellman-Ford&#…...
答案解析——C语言—第3次作业—算术操作符与关系操作符
本次作业链接如下: C语言—第3次作业—算术操作符与关系操作符 1.在C语言中,表达式 7 / 2 的结果是多少? - A) 3.5 - B) 3 - C) 4 - D) 编译错误 答案:B) 3 解析: 在C语言中,当两个整数进行除法运算时&…...
【数据结构】二叉树的链式实现
树是数据结构中非常重要的一种,在计算机的各方个面都有他的身影 此篇文章主要介绍二叉树的基本操作 目录 二叉树的定义:二叉树的创建:二叉树的遍历:前序遍历:中序遍历:后序遍历: 二叉树节点个数…...
八、QLayout 用户基本资料修改(Qt5 GUI系列)
目录 一、设计需求 二、实现代码 三、代码解析 四、总结 一、设计需求 在很多应用程序中会有用户注册或用户编辑信息等界面。本文就设计一个用户信息编辑界面。要求包含用户名、姓名、性别、部门、年龄、头像、个人说明等信息。 二、实现代码 #ifndef DIALOG_H #define D…...
tomcat、java、maven
JDK|JRE Tomcat官网介绍的更清楚 Java 环境安装 安装 wget https://builds.openlogic.com/downloadJDK/openlogic-openjdk/8u392-b08/openlogic-openjdk-8u392-b08-linux-x64.tar.gz tar -xf openlogic-openjdk-8u392-b08-linux-x64.tar.gz mv openlogic-openjdk…...
IDEA好用插件
CodeGlance Pro 右侧代码小地图 Git Commit Template git提交信息模板 IDE Eval Reset 无限试用IDEA Maven Helper 图形化展示Maven项 One Dark theme 好看的主题 SequenceDiagram 展示方法调用链 Squaretest 生成单元测试 Translation 翻译 Lombok lombok插件…...
面试官:CSS3新增了哪些新特性?
面试官:CSS3新增了哪些新特性? 一、是什么 css,即层叠样式表(Cascading Style Sheets)的简称,是一种标记语言,由浏览器解释执行用来使页面变得更美观 css3是css的最新标准,是向后兼…...
Vite5 + Vue3 + Element Plus 前端框架搭建
为了开发一套高效使用的 Vite5 + Vue3 + Element Plus 前端框架,你可以按照以下步骤进行。话不多说,先上演示地址:Vue Shop Vite。 1, 安装开发环境 开发之前,确保你的电脑已经安装了 Node.js(建议使用最新稳定版 LTS),然后安装 Vite CLI。在命令行中运行以下命令: …...
STM32 内部 EEPROM 读写
STM32 的某些系列 MCU 自带 EEPROM。笔者使用的 STM32L151RET6 自带 16 KB 的 EEPROM,可以用来存储自定义的数据。在芯片选型时,自带 EEPROM 也可以作为一个考量点,省去了在外接 EEPROM 的烦恼。 下面简单介绍下 STM32 内部 EEPROM 的读写流…...
androidStudio sync failed GradlePropertiesModel (V2)
大家在增加模块的时候经常遇到吧?重启后就好了。 Cannot get GradlePropertiesModel (V2) for project ‘GradleProject{path’:app’}’ 然而,今天开机以后,无论如何,点击gradle的大象图标(Sync Project with Gradle Files)&…...
结构方程模型(SEM)
结构方程模型(Structural Equation Modeling)是分析多变量间因果关系的利器,在众多学科领域具有巨大应用潜力。我们前期推出的《基于R语言结构方程模型》课程通过结构方程原理介绍、结构方程全局和局域估计、模型构建和调整、潜变量分析、复合…...
基于UDP的网络编程
UDP服务端 #ifdef _WIN32 #define _WINSOCK_DEPRECATED_NO_WARNINGS #define close closesocket #include <winsock2.h> #else #include <arpa/inet.h> #include <netdb.h> #include <netinet/in.h> #in…...
vue判断组件有没有传入的slot有就渲染slot没有就渲染内部节点
GPT4国内站点:海鲸AI 在 Vue 中,你可以使用 $slots 对象来检查是否有特定的插槽内容被传递给组件。Vue 3 中的 $slots 是一个对象,其中包含了所有插槽的引用。如果插槽没有内容,对应的插槽属性将会是 undefined。 下面是一个例子…...
MS713/MS713T:CMOS 低压、4Ω四路单刀单掷开关,替代ADG713
产品简述 MS713/MS713T 是一款单芯片 CMOS 4 路可选择开关,具有低 功耗、高开关速度、低导通阻抗、低漏电和高带宽特性。其工作 电压范围是 1.8V 到 5.5V ,可以广泛应用在电池供电仪器仪表、新 一代的模数转换和数模转换系统中。其高带宽特性可用在 …...
Android 内容生成pdf文件
1.引入itext7 implementation com.itextpdf:itext7-core:7.1.13上面比较大,可以直接下载需要集成的jar包 implementation files(libs\\layout-7.1.13.jar) implementation files(libs\\kernel-7.1.13.jar) implementation files(libs\\io-7.1.13.jar) implementatio…...
Javaweb-日程管理
094.日程管理第二期_准备数据库和实体类_哔哩哔哩_bilibili navicat 下载 学生认证: Navicat 教育版 - 学生许可证 | Navicat navicat连接mysql 使用navicat连接mysql数据库创建数据库、表、转储sql文件,导入sql数据_哔哩哔哩_bilibili...
SwiftUI之深入解析如何创建一个灵活的选择器
一、前言 在 Dribbble 上找到的设计的 SwiftUI 实现时,可以尝试通过一些酷炫的筛选器扩展该项目以缩小结果列表。筛选视图将由两个独立的筛选选项组成,两者都有一些可选项可供选择。但是,在使用 UIKit 时,总是将这种类型的视图实…...
【模拟量采集1.2】电阻信号采集
【模拟量采集1.2】电阻信号采集 1 怎么测?2 测输入电阻电压即转为测模拟电压值,这里需要考虑选用怎样的辅助电阻?3 实际电路分析3.1 在不考虑 VCC-5V 电压的纹波等情况时(理想化此时输入的 VCC 就是稳定的 5V)3.2 若考…...
c++牛客总结
一、c/c语言基础 1、基础 1、指针和引用的区别 指针是一个新的变量,指向另一个变量的地址,我们可以通过这个地址来修改该另一个变量; 引用是一个别名,对引用的操作就是对变量本身进行操作;指针可以有多级 引用只有一…...
ts相关笔记(基础必看)
推荐一下小册 TypeScript 全面进阶指南,此篇笔记来源于此,记录总结,加深印象! 另外,如果想了解更多ts相关知识,可以参考我的其他笔记: vue3ts开发干货笔记TSConfig 配置(tsconfig.…...
Docker随笔
OverView 为什么需要Docker 如果我需要部署一个服务,那么我需要提前部署其他应用栈,不同的应用栈会依赖于不用的操作系统和环境。这样做会产生一些负面影响: 不同版本依赖较长的部署时间不同的Dev/Test/Prod环境 这时我们需要一个工具去解…...
uni-app 前后端调用实例 基于Springboot
锋哥原创的uni-app视频教程: 2023版uniapp从入门到上天视频教程(Java后端无废话版),火爆更新中..._哔哩哔哩_bilibili2023版uniapp从入门到上天视频教程(Java后端无废话版),火爆更新中...共计23条视频,包括:第1讲 uni…...
vue3+ts开发干货笔记
总结一下在vue3中ts的使用。当篇记录部分来自于vue官网,记录一下,算是加深印象吧。 纯干笔记,不断补充,想到什么写什么,水平有限,欢迎评论指正! 另外,如果想了解更多ts相关知识&…...
Android开发新的一年Flag
在新的一年里,为了提升Android开发技能,实现更优质的应用程序,我们制定了2024的新年Flag。这些Flag涵盖了技术学习、代码优化、架构升级、用户体验等多个方面,旨在帮助我们成为更优秀的Android开发者。 1. 学习新技术 1.1. Andr…...
好的OODA循环与快慢无关
OODA循环是指观察(Observe)、导向(Orient)、决策(Decide)和行动(Act)这四个步骤的循环过程。它是一种决策和行动的框架,旨在帮助个人或组织更快地适应和应对变化。 OODA循…...
Android 车联网——CarUserService介绍(十三)
一、简介 CarUserService 是 Android 汽车平台的一个组件,它用于管理和提供车辆用户信息。该组件可以让开发者创建和管理与车辆用户相关的数据和配置,包括车辆拥有者和乘客的个人信息、偏好设置、用户偏好配置文件等。 CarUserService 提供了以下功能和特性: 用户配置管理:…...
【开题报告】基于微信小程序的母婴商品仓库管理系统的设计与实现
1.选题背景 随着社会经济的发展和家庭生活水平的提高,母婴商品市场逐渐兴起。然而,传统的母婴商品仓库管理方式存在着许多问题,如信息不透明、操作繁琐等。为了提高仓库管理的效率和准确性,基于微信小程序的母婴商品仓库管理系统…...
分布式锁相关问题(三)
Redis实战精讲-13小时彻底学会Redis 一、什么是分布式锁? 要介绍分布式锁,首先要提到与分布式锁相对应的是线程锁、进程锁。 l 线程锁:主要用来给方法、代码块加锁。当某个方法或代码使用锁,在同一时刻仅有一个线程执行该方法或该…...
grep!Linux系统下强大的文本搜索工具!
grep!Linux系统下强大的文本搜索工具! grep是一个强大的文本搜索工具,它可以在文件中查找包含指定字符串的行。grep的基本语法如下: grep [选项] "搜索字符串" 文件名其中,选项可以是以下几种:…...
(学习打卡1)重学Java设计模式之设计模式介绍
前言:听说有本很牛的关于Java设计模式的书——重学Java设计模式,然后买了(*^▽^*) 开始跟着小傅哥学Java设计模式吧,本文主要记录笔者的学习笔记和心得。 打卡!打卡! 设计模式介绍 一、设计模式是什么? …...
做网站哪个靠谱/汕头seo推广外包
目录循环依赖多级缓存一级缓存二级缓存当循环依赖遇上AOP三级缓存Spring三级缓存源码实现总结循环依赖 BeanFactory作为bean工厂管理我们的单例bean,那么肯定需要有个缓存来存储这些单例bean,在Spring中就是一个Map结构的缓存,key为beanName&…...
网站建设是基础服务吗/网站如何宣传推广
目录 1、斐波那契数列 2、爬楼梯 1、斐波那契数列 /*** 509. 斐波那契数* 斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:** F(0) 0&#…...
如何找网站做推广/长尾关键词搜索网站
一、SSH协议SSH是一种协议标准,其目的是实现安全远程登录以及其它安全网络服务。二、SSH登录过程SSH登录主要分为两个阶段:1)协商客户端和服务端双方通信所使用的共享密钥,并用这个共享密钥实现后续会话过程的对称加密;…...
长宁区公司网站建设/谷歌浏览器网页版在线
jquery如何实现excel解析,把excel中复以文本形式的复制,然后解析。Jquery无法解析Excel这个交给后端完成就好了jquery调用excel回归分析服务端代码:复制代码代码如下:ServletOutputStream out null;try{//设置csv信息response.setContentType("text/csv");String di…...
网站建设活动/seo外包 杭州
操作系统复习一,单项选择题1.在下列性质中,()不是分时系统的特征。a. 多路性b. 交互性c. 独占性d.成批性2.分时系统的响应与下列哪一个因素无关。()a. 时间片长短b. 系统时钟的频率c. 终端用户数d.主存和外存之间的信息交换量3. 所谓临界区是指()。a. 一个缓冲区b. …...
web网站建设与计划论文/大连网站优化
点击上方“程序员小灰”,选择“置顶公众号”有趣有内涵的文章第一时间送达!本文授权转载自 CSDN 与言则整理圣诞将至,还不赶快微信官方 求顶圣诞帽~~点开朋友圈,你会发现许多好友的头像,都戴着一顶红色的圣诞帽&#x…...