引言
最短路分为一些情况，主要有分类：非负or含负、边权or点权、单源点or全源点。
含有负权时还需要判断有无负环，而如果是点权则可以通过将一个点分裂成入点和出点，从而将点权转化为边权。
至于全源最短路好像考察的很少，Floyd也非常简单粗暴，而Johnson算法的势能思想是将负权图转化为非负权图从而可以跑Dijkstra。
在这篇文章中会设计到以下算法：
- 朴素Dijkstra和堆优化Dijkstra，处理非负权图最优
- Bellman-Ford，常用于判断负环和限制经过边数
- SPFA，Bellman-Ford的队列优化形式，容易被特殊构造图卡死导致TLE
- Floyd，基于DP的全源最短路，简单粗暴
- Johnson，通过一次SPFA将图转化为非负权图后，进行V次Dijkstra
说明
disti数组是记录目前i点距离源点的最距离
disti,j是记录目前点i到点j的最短距离
初始的dist值为极大值inf
(i,j)表示从i到j这条边的边权
松弛，指i点当前的disti可以优化成distj+(j,i)，即通过j点中转到i点比当前从源点直接到i点的距离要短，这一优化过程叫松弛。
在复杂度分析中，V表示点的数量，E表示边的数量
Dijkstra
Dijkstra的算法思想是贪心,下面是算法流程：
- 先使用源点，同时确定了源点的最短路径就是0，对所有点尝试松弛后。
- 进入下一轮，寻找未使用过（当前只有源点使用过）的点中距离源点最小的点记为i，使用i点，同时能够确定i点的最短路径就是当前的disti，然后用i点对所有点尝试松弛。
- 重复第2个操作V次，就可以将所有点的最短路求出来。
堆优化的思路就显而易见了，将松弛过的点加入小根堆中，随后每一次就可以直接取出来距离最小的点。
复杂度分析
朴素版Dijkstra一共会进行n轮操作，每次操作尝试松弛所有点，所以复杂度是O(V2)
堆优化版Dijkstra，取堆顶复杂度为O(logV)，共进行V次，因此为O(VlogV)，在松弛过程中，会遍历所有边尝试松弛，每次将松弛后的点加入堆中O(logV)，进行E次，因此为O(ElogV)，总共为O((V+E)logV)，一般写成O(ElogV)
Dijkstra算法的正确性建立在非负权图上最短路没有后效性，而为了其优秀的复杂度，可以通过Johnson势能转化思想将负权图转化为非负权图。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| void Dijkstra()
{
dist.assign(n+1,INF);
dist[s]=0;
vector<bool>vis(n+1,0);
for(int i=1;i<=n;i++)
{
int u=-1,d=INF;
for(int j=1;j<=n;j++)
{
if(vis[j]||dist[j]>=d)continue;
u=j;
d=dist[j];
}
if(u==-1)break;
vis[u]=1;
for(auto [v,w]:edge[u])
{
dist[v]=min(dist[v],dist[u]+w);
}
}
}
void Dijkstra()
{
priority_queue<pair<int,int>>q;
dist.assign(n+1,INF);
q.emplace(0,s);
dist[s]=0;
while(!q.empty())
{
auto [d,u]=q.top();
q.pop();
d=-d;
if(d>dist[u])continue;
for(auto [v,w]:edge[u])
{
if(d+w<dist[v])
{
dist[v]=d+w;
q.emplace(-dist[v],v);
}
}
}
}
|
Bellman-Ford
Bellman-Ford算法十分简单，常用来判断图上有无负环（前提是源点可到达任意点），其流程如下：
- 遍历所有的边，尝试对当前最短路进行优化。
- 一共重复V-1次操作1。
- 再进行第V次操作1，如果还存在可以松弛的边，那么说明存在负环。
复杂度分析
总共进行V次操作，每次操作遍历所有边，时间复杂度O(V×E)
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| bool BF()
{
dist.assign(n+1,INF);
dist[s]=0;
for(int i=1;i<=n-1;i++)
{
bool fg=0;
for(int u=1;u<=n;u++)
{
for(auto [v,w]:edge[u])
{
if(dist[v]>dist[u]+w)
{
fg=1;
dist[v]=dist[u]+w;
}
}
}
if(!fg)break;
}
for(int u=1;u<=n;u++)
{
for(auto [v,w]:edge[u])
{
if(dist[v]>dist[u]+w)
{
return 1;
}
}
}
return 0;
}
|
SPFA
在Bellman-Ford中，每次都需要遍历所有的边，而SPFA就是针对这一点进行的优化。
- 在遍历边的过程中，发生松弛的点只有可能发生在之前被松弛过的点所连出的边上。
这就引出来了队列优化，从源点开始，将松弛过的点加入队列，每次从队列中取出一个点并进行下一轮松弛。
而如果一个点在加入队列后，在取出来之前，又被松弛了，则没有必要再加入队伍，因此需要一个在队标记处理。
算法步骤如下：
- 将源点压入队列，标记在队。
- 从队列中取出队头，标记离队后，对该连出的边尝试松弛，如果目标点松弛成功，并且目标点不在队，则将其压入队，标记在队。
- 直到队列为空，或判断出有负环时，结束算法。
- 判断有负环的方法是记录所有点的入队次数，如果入队次数达到N次，说明其进行了V轮松弛，就说明存在负环。
复杂度分析
由于SPFA只是对Bellman-Ford进行了队列优化，并没有做出实质的复杂度降低，因此最坏情况下其复杂度仍为O(V×E)。
不过其在随机图中有着非常出色的速度，期望下可以达到O(E)。
一定要慎用SPFA！！！非必要不使用！！！
SPFA判断负环同样要保证源点可达任意点。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| bool SPFA()
{
dist.assign(n+1,INF);
dist[s]=0;
queue<int>q;
vector<int>vis(n+1,0),cnt(n+1,0);
q.emplace(s);
vis[s]=1;
while (!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(auto [v,w]:edge[u])
{
if(dist[u]+w<dist[v])
{
dist[v]=dist[u]+w;
cnt[v]++;
if(cnt[v]>=n)return false;
if(!vis[v])
{
q.push(v);
vis[v]=1;
}
}
}
}
return true;
}
|
Floyd
Floyd算法本质上是DP。
维护Fk,i,j表示使用前k个节点作为中间节点，从i到j的最短距离。
状态转移如下：
- 如果选择加入第k个节点作为中间节点，则Fk,i,j=Fk−1,i,k+Fk−1,k,j
- 如果不加入第k个节点，则Fk,i,j=Fk−1,i,j
因此最终的状态转移方程为
Fk,i,j=min(Fk−1,i,j,Fk−1,i,k+Fk−1,k,j)
由于k只依赖于k-1，因此可以将三维压缩为二维。
复杂度分析
显然，通过3层循环，Floyd复杂度为O(V3)
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
dist[u][v]=min(dist[u][v],w);
dist[v][u]=min(dist[v][u],w);
}
void Floyd()
{
for(int k=1;k<=n;k++)
{
for(int u=1;u<=n;u++)
{
for(int v=1;v<=n;v++)
{
if(u==v)dist[u][v]=0;
if(dist[u][v]>dist[u][k]+dist[k][v])
{
dist[u][v]=dist[u][k]+dist[k][v];
dist[v][u]=dist[v][k]+dist[k][u];
}
}
}
}
}
|
Johnson
这是一种为了利用Dijkstra的优秀复杂度而设计的算法。
其核心思想在于势能转化，我们进行松弛的目的就是为了在最终算法完成后，对于∀i,j,k,都有如下式子，最短路才正确。
dists,i≤dists,k+(k,i)
我们为了让边权非负，就需要重新修改边权。
通过建立一个超级源点O，连向所有点，且边权均为0，在这张连通图上以O为源点跑SPFA，得到势能Hi。此时同样满足以上式子Hi≤Hk+(k,i)→Hk−Hi+(k,i)≥0，我们使用Ei,j=Hk−Hi+(k,i)≥0作为新的边权。
此时，考虑任意一条从i到j的路径，这里简单描述为i→k→j，那么这条路的
disti,j=Hi−Hk+(i,k)+Hk−Hj+(k,j)=Hi−Hj+(i,k)+(k,j)
因此在对新边权图上的每个点跑完Dijkstra后，从i到j的实际最短路为disti,j−Hi+Hj
为什么在修改边权后的最短路仍为实际最短路?
由于从i到j的任意一条路径和为Hj−Hi+∑(x,y)，其由只与起点i和j相关的常数和路径和构成，因此最终的最短路是与实际最短路相符合的，这也是为什么被称为势能转化的原因。
算法步骤如下：
- 建立超级源点O，对所有点连出一条边权为0的边。
- 以O为源点跑SPFA并判断有无负环，求出势能Hi，若存在负环，则算法终止。
- 进行V次Dijkstra，求出最短路
- 在所求的最短路中，减去起点与终点的势能差。
复杂度分析
一次SPFA最坏的复杂度为O(VE)，而V次Dijkstra的复杂度为O(VElogV)，因此复杂度瓶颈并不在SPFA上。而如果Dijkstra不使用堆优化，那就不如用Floyd了。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| bool SPFA(int s)
{
h.assign(n+1,INF);
h[s]=0;
queue<int>q;
vector<int>vis(n+1,0),cnt(n+1,0);
q.emplace(s);
vis[s]=1;
while (!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(auto [v,w]:edge[u])
{
if(h[u]+w<h[v])
{
h[v]=h[u]+w;
if(!vis[v])
{
q.push(v);
vis[v]=1;
cnt[v]++;
if(cnt[v]>=n)return true;
}
}
}
}
return false;
}
void Dijkstra(int s)
{
priority_queue<pair<int,int>>q;
q.emplace(0,s);
dist[s][s]=0;
while(!q.empty())
{
auto[d,u]=q.top();
q.pop();
d=-d;
if(d>dist[s][u])continue;
for(auto [v,w]:edge[u])
{
if(dist[s][v]>d+w)
{
dist[s][v]=d+w;
q.emplace(-dist[s][v],v);
}
}
}
}
void Johnson()
{
for(int i=1;i<=n;i++)
{
edge[0].emplace_back(i,0);
}
if(SPFA(0))
{
cout<<-1;
return;
}
dist.assign(n+1,vector<int>(n+1,INF));
for(int u=1;u<=n;u++)
{
for(auto &[v,w]:edge[u])
{
w=w+h[u]-h[v];
}
}
for(int i=1;i<=n;i++)Dijkstra(i);
for(int i=1;i<=n;i++)
{
int res=0;
for(int j=1;j<=n;j++)
{
if(dist[i][j]==INF)continue;
dist[i][j]=dist[i][j]-h[i]+h[j];
}
}
}
|
