总结一下图论里的最短路。

Dijkstra 算法

Dijkstra 算法可用于非负权值的图，可以表示为如下流程。

  1. 将源点的距离设为 0，其他点的距离设为无穷大。
  2. 从图中找出距离最小且未标记的点 uu，并标记点 uu。松弛所有与 uu 相邻的节点。（松弛：尝试将 s→vs\rightarrow v 的路径用 s→u→vs\rightarrow u \rightarrow v 的距离更新，即 dis[v]=min(dis[v],dis[u]+w[u][v])）
  3. 重复第二步，直到所有节点都被标记。

如果需要输出路径，可以在松弛成功时记录每个节点的前驱。

根据在第二步找出距离最小的点的处理方法不同，Dijkstra 算法有不同的复杂度。

暴力实现

依次遍历所有 nn 个节点，找出最小权值。这样第二步的复杂度为 O(n)O(n)，总共执行 nn 次，总复杂度为 O(n2)O(n^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
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;

struct Edge{
    int v,w;
};

int dis[N],pre[N];
vector<Edge> G[N];
bool vis[N];

int n,m;
int s;

void dijkstra(){
    // 初始化距离
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;

    for(int i=0;i<n;i++){
        // 暴力实现，找出点 u
        int u;int du=INF;
        for(int j=1;j<=n;j++){
            if(!vis[j] && dis[j]<du){
                u=j,du=dis[j];
            }
        }

        vis[u]=1; // 标记 u
        for(auto edge:G[u]){ // 松弛所有与 u 相连的边
            if(vis[edge.v])continue;
            if(dis[edge.v]>dis[u]+edge.w){ 
                dis[edge.v]=dis[u]+edge.w;
                pre[edge.v]=u;
            }
        }
    }
}

优先队列实现

优先队列实现在稀疏图上更有优势。

因为优先队列不能进行删除操作，所以队列中最多有 mm 个节点（有之前松弛的距离较大的），复杂度为 O(mlog⁡m)O(m\log m)

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
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;

struct Edge{
    int v,w;
};

int dis[N],pre[N];
vector<Edge> G[N];
bool vis[N];

int n,m,s;

struct Node{
    int u,dis;
    bool operator<(const Node& rhs)const{
        return dis>rhs.dis;
    }
};

void dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;

    priority_queue<Node> q;
    q.push({s,0});    

    while(!q.empty()){
        int u=q.top().u;q.pop();
        if(vis[u])continue; // 因为优先队列不能删除   
        vis[u]=1;
        for(auto edge:G[u]){
            if(vis[edge.v])continue;
            if(dis[edge.v]>dis[u]+edge.w){
                dis[edge.v]=dis[u]+edge.w;
                pre[edge.v]=u;
            }
        }
    }
}

Bellman-Ford 算法

Bellman-Ford 算法可以表示为如下流程。

  1. 将源点的距离设为 0，其他点的距离设为无穷大。
  2. 对图中每条边执行松弛操作。
  3. 重复第 2 步，直到没有一条边松弛成功。

可以证明最多只需要松弛 n−1n-1 遍。（因为每次松弛成功最短路的经过的边数就会增加 11，而最短路最多经过 n−1n-1 条边，否则就会出现环）

每次执行松弛操作的复杂度为 O(m)O(m)，故总复杂度为 O(nm)O(nm)。

如果需要输出路径，可以在松弛成功时记录每个节点的前驱。

判断负环

Bellman-Ford 算法可以用来判断图中是否有负环。只需要判断 n−1n-1 次松弛后，如果还能进行松弛操作，则代表有负环。

Bellman-Ford 算法判断负环只能代表从源点 ss 出发可以抵达一个负环，如果图不强连通，不一定能找到图中的负环。因此，可以建立一个超级源点，从超级源点向每个节点建立一条边权为 0 的边，从超级源点开始进行 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
28
29
30
31
32
33
34
35
36
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;

struct Edge{
    int v,w;
};

int dis[N],pre[N]; // 记录数据
vector<Edge> G[N];

int n,m,s;

bool bellman_ford(){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;

    for(int i=1;i<n;i++){
        for(int u=1;u<=n;u++){
            for(auto edge:G[u]){
                if(dis[edge.v]>dis[u]+edge.w){
                    dis[edge.v]=dis[u]+edge.w;
                    pre[edge.v]=u;
                }
            }
        }
    }

    for(int u=1;u<=n;u++){
        for(auto edge:G[u]){
            if(dis[edge.v]>dis[u]+edge.w){
                return 1; // 有负环
            }
        }
    }
    return 0;
}

SPFA 算法

SPFA 算法可以看作是 Bellman-Ford 算法的一个改进。其基本思想是每次进行松弛操作时，只松弛与上次松弛成功的边相连的点。

使用一个队列记录上一轮循环中成功松弛的点。

关于 SPFA，他死了

SPFA 算法的最坏复杂度是 O(nm)O(nm)，意味着你不应该在一张非负权值图上使用 SPFA 算法，会被卡（应该用 dijkstra 算法）。因此 SPFA 算法应该只在图中存在负权边的情况下使用，视作一个 Bellman-Ford 算法的小优化。

判断负环

SPFA 算法也可以判断负环。只要同时记录一个点到源点的最短路经过了几条边。如果经过了大于等于 nn 条边，则有负环。

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
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
const int INF = 0x3f3f3f3f;

struct Edge{
    int v,w;
};

int dis[N],pre[N]; // 记录数据
vector<Edge> G[N];
int cnt[N]; // 代表到节点u的最短路经过几条边
bool in_queue[N];

int n,m,s;

bool spfa(){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;

    queue<int> q;
    q.push(s);in_queue[s]=1;

    while(!q.empty()){
        int u = q.front();q.pop();
        in_queue[u]=0;
        for(auto edge:G[u]){
            if(dis[edge.v]>dis[u]+edge.w){
                dis[edge.v]=dis[u]+edge.w;
                pre[edge.v]=u;
                cnt[edge.v]=cnt[u]+1;
                if(cnt[edge.v]>=n)return 1; // 有负环
                if(!in_queue[edge.v]){
                    q.push(edge.v);in_queue[edge.v]=1;
                }
            }
        }
    }
    return 0;
}

Floyd 算法

一个多源最短路算法。使用三重循环实现。还可以用来找到图中的最小环。（最小环相关介绍见 最小环问题）

1
2
3
4
5
6
7
8
9
10
11
void floyd(){
    memset(dis,0x3f,sizeof(dis));

    for (int k=1;k<=n;k++) {
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=n;j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

总结

总结一下这四个算法。

Dijkstra 算法 Bellman-ford 算法 SPFA 算法 Floyd 算法
算法类型 单源最短路径 单源最短路径 单源最短路径 多源最短路径
图限制 非负权值图 - - -
复杂度 暴力：O(n2)O(n^2)
优先队列：O(mlog⁡m)O(m\log m)		 O(nm)O(nm) 最坏 O(nm)O(nm) O(n3)O(n^3)
其余应用 - 判断负环 判断负环 找最小环