最短路算法

单源最短路

单源最短路的意思就是一个起点,算出到其他点的最短路,这里介绍三种算法,bellman-ford,spfa和dijkstra

BF算法

算法思想

BF是bellman_ford的简称,算法的想法非常简单,进行$|V|-1$次操作,每次操作对所有的边松弛。
松弛可以形象的理解为更新值,比如有一条从$u$到$v$的边,如果$u$上的值加上边的长度小于$v$上的值,那么就更新$v$上的值。
为什么这样做是对的呢?我们可以回顾整个过程,第一次操作,我们一定能将起点出去的点中的某一个点更新为最小值(这个点以后不会被更新),关于这点可以用反证法证明,如果没有一个点是更新完毕的,那么从起点到这个点必然存在一条比起点到这个点的边更短的路径,与假设矛盾。故而每次我们至少能确定一个点,所以总共需要$|V|-1$次(起点不用更新)。
最开始的图,0是起点


初始化

第一次松弛更新了1,2,3三个点

最后全部更新好了

算法实现

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
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define INF 1008611
#define MAX_V 1003
using namespace std;
struct edge{
int to,cost;
edge(int tt,int cc):to(tt),cost(cc){}
edge(){}
};
vector<edge> G[MAX_V];//用vector存图,点的编号从1开始
int V,E;//点数和边数
int d[MAX_V];//最短路
//最短路算法,s是起点
void BF(int s){
fill(d+1,d+1+V,INF);
d[s]=0;
for(int i=0;i<V-1;i++){
for(int u=1;u<=V;u++)
for(int j=0;j<G[u].size();j++){
int v=G[u][j].to,c=G[u][j].cost;
if(d[u]+c<d[v])
d[v]=d[u]+c;
}
}
}
int main(){
cin>>V>>E;
while(E--){
int u,v,c;
cin>>u>>v>>c;
G[u].push_back(edge(v,c));
}
BF(1);
for(int i=1;i<=V;i++)
cout<<i<<" "<<d[i]<<endl;
return 0;
}

复杂度分析

复杂度很明显是$O(V*E)$,在完全图的时候,会变成$O(V^3)$

SPFA算法

SPFA算法又叫做bellman-ford队列优化,至于为啥叫SPFA我也不知道。

算法思想

纵观整个BF算法,我们可以用宽度优先搜索来代替V-1次的暴力松弛,每次用队列头部的元素去更新其他点,如果将一个点更新成功,就将这个点加入队列,直到更新不动为止。
可以证明,这样做和BF本质上是一样的。但这样做有个好处,这个好处就在于我们可以记录一个点是否在队列中,如果这个点在队列中,那么我们知道这个点一定会被拿出来松弛,那么当这个点被更新的时候,我们就不用讲他加入队列了。如此,就大大改进了BF算法。

算法实现

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
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 1008611
#define MAX_V 1003
using namespace std;
struct edge{
int to,cost;
edge(int tt,int cc):to(tt),cost(cc){}
edge(){}
};
vector<edge> G[MAX_V];//用vector存图,点的编号从1开始
int V,E;//点数和边数
int d[MAX_V];//最短路
queue<int> que;//搜索用的队列
bool inQue[MAX_V];//判断是否在队列中
//最短路算法,s是起点
void SPFA(int s){
fill(d+1,d+1+V,INF);
d[s]=0;
que.push(s);
inQue[s]=1;
while(que.size()){
int u=que.front();que.pop();
inQue[u]=0;
for(int i=0;i<G[u].size();i++){
int v=G[u][i].to,c=G[u][i].cost;
if(d[u]+c<d[v]){
d[v]=d[u]+c;
if(!inQue[v]){
inQue[v]=1;
que.push(v);
}
}
}
}
}
int main(){
cin>>V>>E;
while(E--){
int u,v,c;
cin>>u>>v>>c;
G[u].push_back(edge(v,c));
}
SPFA(1);
for(int i=1;i<=V;i++)
cout<<i<<" "<<d[i]<<endl;
return 0;
}

算法复杂度

这个算法的复杂度是个迷,据传是$O(k*E)$,其中$k$是个不大的常数。

Dijkstra算法

算法思想

我们依旧用宽度优先搜索的角度思考BF算法,我们发现,如果我们每次都将最小的值从队列中拿出,那么拿出来的一定是已经更新好了的(同样可以用反证法证明),所以只要我们将队列变成堆,就能快速处理最短路了。
还是刚刚那个图,最开始将0号节点加入堆

现在从堆中拿出最小的数0,用他更新1,2,3,并把1,2,3加入堆

现在堆里面最小的数是2号节点,说明2号节点已经更新好了,那么用2号节点去更新其他节点

最好都更新好了

算法实现

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
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 1008611
#define MAX_V 1003
using namespace std;
struct edge{
int to,cost;
edge(int tt,int cc):to(tt),cost(cc){}
edge(){}
};
vector<edge> G[MAX_V];//用vector存图,点的编号从1开始
int V,E;//点数和边数
int d[MAX_V];//最短路
struct node{
int u,c;
node(int uu,int cc):u(uu),c(cc){}
node(){}
bool operator<(const node &a)const {
return c>a.c;
}
};
priority_queue<node> que;
//最短路算法,s是起点
void dijkstra(int s) {
while (que.size())que.pop();
fill(d + 1, d + V + 1, INF);
que.push(node(s, 0));
d[s] = 0;
while (que.size()) {
node now = que.top();
que.pop();
int u = now.u, c = now.c;
if (d[u] < c)continue;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].to;
if (d[v] > d[u] + G[u][i].cost) {
d[v] = d[u] + G[u][i].cost;
que.push(node(v, d[v]));
}
}
}
}
int main(){
cin>>V>>E;
while(E--){
int u,v,c;
cin>>u>>v>>c;
G[u].push_back(edge(v,c));
}
dijkstra(1);
for(int i=1;i<=V;i++)
cout<<i<<" "<<d[i]<<endl;
return 0;
}

算法复杂度

由于我们至少将所有边遍历一次,所以我们需要$O(E)$的时间,堆优化使得我们在搜索时将一个$V$的复杂度降到$logV$,所以时间复杂度为$O(E+VlogV)$


多源最短路

如果我们想知道任意两个点之间的最短路,这时候可以暴力跑n次单源最短路,也可以用floyd算法

Floyd算法

这个算法的特点就是非常好写

算法思想

Floyd算法运用了动态规划的思想,对于一个最短路径(u,v)而言,我们一定是从u到了k,再从k到v。所以我们只要知道了(u,k)和(k,v)的最短路,那么我们就能得到(u,v)的最短路。
所以暴力枚举就好

算法实现

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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX_V 102
#define INF 1008611
using namespace std;
int d[MAX_V][MAX_V];
int V,E;
int main(){
cin>>V>>E;
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++)
d[i][j]=(i==j?0:INF);
while(E--){
int u,v,c;
cin>>u>>v>>c;
d[u][v]=c;
}
for(int k=1;k<=V;k++)
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++)
d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++)
cout<<i<<" "<<j<<" "<<d[i][j]<<endl;
return 0;
}

算法复杂度

很明显,复杂度是$O(V^3)$