最短路基础算法学习

特点汇总

最短路算法	Floyd	Bellman–Ford	Dijkstra	Johnson
最短路类型	每对结点之间的最短路	单源最短路	单源最短路	每对结点之间的最短路
作用于	任意图	任意图	非负权图	任意图
能否检测负环？	能	能	不能	能
时间复杂度	$O(N^3)$	$O(NM)$	$O(M \log M)$	$O(NM \log M)$

Floyd 算法

简介

用来求任意两个结点之间的最短路
复杂度较高 $O(n^3)$ 容易实现
使用与任何图，不管有向无向，边权正负，但是最短路必须存在，不能存在负环(即边权之和为负数的环，可以无限次通过减少所求答案)

实现

定义一个数组 $f[k][x][y]$，表示只允许经过点 1 到 $k$ (包含点 1 到点 $k$ 的子图，$x$ $y$ 不一定在子图中)，点 $x$ 到点 $y$ 的最短路长度

$f[n][x][y]$ 即为 $x$ 到 $y$ 的最短路长度

$f[0][x][y]$: $x$ 和 $y$ 之间有联通路时为二者的边权，若无则为 $+\infty $ 如果 $x == y$ 则为 0

$f[k][x][y] = \min(f[k-1][x][y], f[k-1][x][k]+f[k-1][k][y])$（$f[k-1][x][y]$，为不经过 $k$ 点的最短路径，而 $f[k-1][x][k]+f[k-1][k][y]$，为经过了 $k$ 点的最短路）。

可以发现第一维是无影响的，因此空间复杂度可以优化到 $O(n^2)$

1
2
3
4
5
6
7
8
9


void floyd(){
    for(int k=1;k<=n;k++){
        for(int x=1;x<=n;x++){
            for(int y=1;y<=n;y++){
                f[x][y]=min(f[x][y],f[x][k]+f[k][y]);
            }
        }
    }
}

例题

洛谷 B3647

 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


#include <bits/stdc++.h>
using namespace std;

int n,m;
int f[110][110];
int inf = 1e9;

void floyd(){
    for(int k=1;k<=n;k++){
        for(int x=1;x<=n;x++){
            for(int y=1;y<=n;y++){
                f[x][y]=min(f[x][y],f[x][k]+f[k][y]);
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        if(!f[x][y])f[x][y]=f[y][x]=w;
        else f[x][y]=f[y][x]=min(f[x][y],w);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(f[i][j])continue;
            if(i==j)f[i][j]=0;
            else f[i][j]=inf;
        }
    }
    floyd();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cout<<f[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

Bellman-Ford 算法

简介

基于松驰操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断

SPFA 是 Bellman-Ford 的一种实现

松驰操作指的是 $dis[v] = \min(dis[v], dis[u] + w[u][v])$

Bellman-Ford 算法做的就是不断尝试对图上每一条边进行松驰，每一轮循环都尝试对图上所有的边进行一次松驰操作，当一次循环中没有成功的松驰操作时，算法停止

整个算法最多进行 $n - 1$ 轮松驰操作，所以时间复杂度为 $O(nm)$

如果从 $s$ 点出发，抵达一个负环，松驰会无休止的进行下去，如果 $n - 1$ 轮后还有能松驰的边，说明从 $s$ 点出发，能够抵达一个负环

如果以 $s$ 点跑，没有找到负环，只能说明从 $s$ 点无法到达负环，如果要判断图上是否有负环，需要建立一个超级源点 $o$ 对图上每个点连一条权值为 0 的边，再以 $o$ 为起点跑一遍 Bellman-Ford

实现

 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


struct Node{
    int u,v,w;
};

vector<Node>edge;
int dis[10100],u,v,w;
int n,m;
const int INF = 1e9;

bool bellmanford(int n,int s){
    memset(dis,INF,sizeof(dis));
    dis[s]=0;
    bool flag=false;
    for(int i=1;i<=n;i++){
        flag=false;
        for(int j=0;j<edge.size();j++){
            u=edge[j].u,v=edge[j].v,w=edge[j].w;
            if(dis[u]==INF)continue;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                flag=true;
            }
        }
        if(!flag)break;
    }
    return flag;
}

队列优化 SPFA

很显然，只有上次被松驰的点所连接的边，才可能进行下一次的松驰操作

可以用队列来维护可能引起松驰操作的点

SPFA 也可以用于判断 $s$ 是否能抵达负环，只需记录最短路经过了多少条边即可，若经过了至少 $n$ 条边，说明 $s$ 可以抵达一个负环

 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


struct Node{
    int v,w;
};

vector<Node>edge[N];
int dis[N],cnt[N],vis[N];
queue<int>q;

bool spfa(int n,int s){
    memset(dis,63,sizeof(dis));
    memset(cnt,0,sizeof(cnt));
    memset(vis,0,sizeof(vis));
    dis[s]=0,vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto x:edge[u]){
            int v=x.v,w=x.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n)return false;
                if(!vis[v])q.push(v),vis[v]=1;
            }
        }
    }
    return true;
}

例题

洛谷 P3385

Bellman-Ford

SPFA

Dijkstra 算法

简介

求解 非负权图 上单源最短路径

将点分为两个集合，一个为已确定最短路径的点集 $s$，另一个为未确定最短路长度的点集 $t$，初始状态所有点都在 $t$ 中

初始化 $dis[s] = 0$, 其他点的 $dis$ 均为 $+\infty $
然后重复下列操作：
(1) 从 $t$ 中取一个最短路长度最小的点，移到 $s$ 中
(2) 对刚加入 $s$ 中的点进行所有出边的松驰操作
直到 $t$ 为空，算法结束

暴力实现时间复杂度为 $O(n^2)$
堆优化时间复杂度 $O(m \log n)$

实现

暴力

 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


struct Node{
    int y,v;
    Node(int _y,int _v){y=_y;v=_v;}
};   //开一个结构体用于储存边的信息，y 代表这条边通向哪，v 代表这条边的边权

int n,m,u,v,w,s,t,dist[N];
bool vis[N];
vector<Node>edge[N];//edge 数组的下标就是边的起始点，Node 中的 y 代表这条边通向哪个点

void dijkstra(int s,int t){//s 指代起点，t 指代终点
    memset(vis,0,sizeof(vis));
    memset(dist,127,sizeof(dist)); //初始将所有点的最短路都设置为无穷大 
    dist[s]=0;//起点到自己的距离为 0
    for(;;){
        int x=-1;//x 是这一轮循环中找到的最短路径
        for(int i=1;i<=n;i++){
            if(!vis[i]&&dist[i]<(1<<30))//如果当前这个点没被更新过，并且到达它的最短路不是初始化的无穷大，我们就考虑他是不是当前的最优选择
                if(x==-1||dist[i]<dist[x])x=i;//如果 x 还未被更新，或者到这个点的最短路比之前选的更短，我们就更新 x 
        }
        if(x==t||x==-1)break;//如果 x 为终点，或遍历所有点后 x 还没更新，就终止算法
        vis[x]=1;//标记当前这个 x 避免之后重复使用
        for(auto i:edge[x]){//遍历以 x 这个点为起点的所有边
            dist[i.y]=min(dist[i.y],dist[x]+i.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


struct Node {
    int y, v;
    Node(int _y, int _v) { y = _y, v = _v; }
};

int n, m, s, t, dist[100005];
vector<Node> edge[100005];
set<pair<int, int>> q;

void dijkstra(int s, int t) {
    q.clear();
    memset(dist, 127, sizeof(dist));
    dist[s] = 0;
    for (int i = 1; i <= n; i++) q.insert({dist[i], i});
    for (; !q.empty();) {
        int x = q.begin()->second;
        q.erase(q.begin());
        if (x == t || dist[x] > 1 << 30) break;
        for (auto i : edge[x]) {
            if (dist[x] + i.v < dist[i.y]) {
                q.erase({dist[i.y], i.y});
                dist[i.y] = dist[x] + i.v;
                q.insert({dist[i.y], i.y});
            }
        }
    }
    cout << dist[t] << endl;
}

例题

洛谷 P1339

 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


#include <bits/stdc++.h>
using namespace std;

struct Node {
    int y, v;
    Node(int _y, int _v) { y = _y, v = _v; }
};

int n, m, s, t, dist[100005];
vector<Node> edge[100005];
set<pair<int, int>> q;

void dijkstra(int s, int t) {
    q.clear();
    memset(dist, 127, sizeof(dist));
    dist[s] = 0;
    for (int i = 1; i <= n; i++) q.insert({dist[i], i});
    for (; !q.empty();) {
        int x = q.begin()->second;
        q.erase(q.begin());
        if (x == t || dist[x] > 1 << 30) break;
        for (auto i : edge[x]) {
            if (dist[x] + i.v < dist[i.y]) {
                q.erase({dist[i.y], i.y});
                dist[i.y] = dist[x] + i.v;
                q.insert({dist[i.y], i.y});
            }
        }
    }
    cout << dist[t] << endl;
}

int main() {
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        edge[u].push_back(Node(v, c));
        edge[v].push_back(Node(u, c));
    }
    dijkstra(s, t);
    return 0;
}

Johnson 全源最短路径算法

实现

为了实现有负权图上的 Dijkstra，我们可以新建一个虚拟节点 $o$，从这个点向其他所有点连一条边权为 0 的边

接下来用 Bellman-Ford 求出节点 $o$ 到其他所有点的最短路，记为 $h[i]$

假如存在一条从 $u$ 到 $v$，边权为 $w$ 的边，则将其边权重设为 $w + h[u] - h[v]$

接下来以每个点为起点，跑 $n$ 轮 Dijkstra 即可求出任意两点间的最短路了

该算法时间复杂度是 $O(nm \log m)$