浅谈最短路算法

浅谈最短路算法

封面来源

Pixiv THEM-95671915

浅谈最短路算法

Floyd

  • 复杂度较高(也就3个for循环)

  • 不能有负环

  • 多源最短路(跑一遍后所有点间的最短路都出来了)

  • 就是个暴力

思路

对于一个点对$(s,t)$​来说,如下图,$1 \to 2$的最短路是$ 1\to 3 \to 2$​,这就是Floyd的中心思想

graph

核心代码
1
2
3
4
5
6
7
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[k][x][y]=min(f[k-1][x][y],f[k-1][x][k]+f[k-1][k][y]);
}
}
}

但是显然第一维对结果无影响,所以可以简化为一个二维数组
$$
\begin{align*}
\begin{split}
f(i,j)=min(f(i,j),f(i,k)+f(k,j));
\end{split}
\end{align*}
$$
综上,时间复杂度为$O(N^3)$,空间复杂度为$O(N^2)$

Bellman-Ford

  • 支持负边权

  • 单源最短路

  • 可以优化为SPFA

思路

设源点为$S$

$dis(t)$​​表示$S \to t$​​的最短路

$ relax(u,v)$ 操作指
$$
\begin{align*}
dis(v)=min(dis(v),dis(u)+len(u,v));
\end{align*}
$$
不就是上面的那个三角形不等式吗?

那么Bellman-Ford算法如下

1
while(1) for each edge(u,v) relax(u,v);

当一次循环中没有松弛操作成功时停止

核心代码
1
2
3
4
5
6
7
8
9
10
11
relax(u,v){
dis[v]=min(dis[v],dis[u]+len(u,v));
}
for(i,1,n){
dis[i]=len(S,i);
}
for(i,1,n){
for each edge(u,v){
relax(u,v);
}
}

复杂度为$O(NM)$

队列优化版Bellman Ford: SPFA

原名Shortest Path Faster Algorithm(太自信了

减少一些无用的松弛操作,只有上一次被松弛的点所连的边才可能引起下一次松弛,用队列维护哪些节点可能会引起松弛操作,就只用访问必要的边了

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void spfa(int s){
queue<int> q;
FOR(i,1,n){
dis[i]=inf;
}
dis[s]=0;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u]=0;
Graph(u){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
}

复杂度$O(N,M)$

Dijkstra

发音/ˈdikstrɑ/(

  • 非负权图
思路

BFS

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
voivoid dijk(int s){
for(int i=0;i<=n;i++)
dis[i]=inf,vis[i]=0;
priority_queue<pii,vector<pii>,greater<pii> > q;
q.push(make_pair(dis[s]=0,s));
while(!q.empty()){
pii t=q.top();q.pop();
int x=t.second;
if(vis[x])continue;
vis[x]=1;
Graph(x){
int v=e[i].v;
if(dis[x]+e[i].w<dis[v]){
dis[v]=dis[x]+e[i].w;
q.push(make_pair(dis[v],v));
}
}
}
}

复杂度为 $O(m\log n)$

作者

Steve Li

发布于

2021-10-18

更新于

2022-01-23

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×