# 最短路

最短路算法的分类：

单源最短路
- 所有边权都是正数
  - 朴素的 Dijkstra 算法 O(n^2) 适合稠密图
  - 堆优化版的 Dijkstra 算法 O(mlog n)（m 是图中节点的个数）适合稀疏图
- 存在负权边
  - Bellman-Ford O(nm)
  - spfa 一般 O(m),最坏 O(nm)
多源汇最短路 Floyd 算法 O(n^3)

# 朴素的 Dijkstra 算法

集合 S：当前已经确定最短距离的点

dist[1] = 0, dist[i] = 正无穷
for v: 1 ~ n
- t <- 不在 s 中的距离最近的点
- s <- t
- 用 t 更新其他点的距离

朴素的 Dijkstra 算法往往是稠密图，用邻接矩阵来存储

# 算法模板

int g[N][N];  // 存储每条边；为稠密阵所以用邻接矩阵存储
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist); //初始化距离  0x3f代表无限大
    dist[1] = 0; //第一个点到自身的距离为0

    for (int i = 0; i < n-1; i ++) //有n个点所以要进行n-1次迭代;第一个到自身距离为0
    {
        int t = -1;     // 在还未确定最短路的点中，寻找到1号点距离最小的点
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true; // t号点的最短路已经确定

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[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

时间复杂是 O(n2+m), n 表示点数，m 表示边数

# 题目

AcWing849. Dijkstra 求最短路 I

# 堆优化版的 Dijkstra 算法

集合 S：当前已经确定最短距离的点

dist[1] = 0, dist[i] = 正无穷
for v: 1 ~ n
- t <- 不在 s 中的与起始点距离最近的点；小顶堆维护 O(logN)
- s <- t; O(1)
- 用 t 更新其他点的距离 ; O(mlogN)

稀疏图用堆优化版的 Dijkstra 算法

# 时间复杂度

O(mlogN)

# 代码实现

堆优化版的 Dijkstra 算法有点像宽搜

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        const int INF = 0x3f3f3f3f;
        typedef pair<int, int> PII; // first:距离; second: 几号点
        vector<bool> st(N+1, false); // 是否已得到最短距离
        vector<int> dist(N+1, INF); // 距离起始点的最短距离
        unordered_map<int, vector<PII>> graph; // 邻接表；u->v,权重w
        priority_queue<PII, vector<PII>, greater<PII>> heap; // 小顶堆；维护到起始点的最短距离和点
        for (auto &t: times){ // 初始化邻接表
            graph[t[0]].push_back({t[2],t[1]});
        }
        heap.push({0, K});
        dist[K] = 0;
        while(heap.size()){
            auto t = heap.top();
            heap.pop();
            int ver = t.second, distance = t.first;
            if (st[ver]) continue; // 之前更新过，是冗余备份
            st[ver] = true;
            for (auto &p: graph[ver]){
                if (dist[p.second] > distance + p.first){ // 用t去更新其他点到起始点的最短距离
                    dist[p.second] = distance + p.first;
                    heap.push({dist[p.second], p.second});
                }
            }
        }
        int ans = 0;
        for (int i = 1; i<=N; i++){
            ans = max(ans, dist[i]);
        }
        if (ans == INF) return -1;
        return ans;
    }
};

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

# Bellman-Ford 算法

# 算法思路

n 个点，m 条边

循环 n 次
- 遍历所有边u->v,权 w (松弛操作)
  - dist[v]=min(dist[v], dist[u]+w)

# 应用

处理有负权边的图
循环次数的含义：循环 K 次后，表示不超过 K 条边的最短距离
有边数限制的最短路，只能用 Bellman-Ford 算法，不能用 spfa 算法
如果有负权回路，最短路不一定存在
Bellman-Ford 算法可以求出是否有负环
- 第 n 循环后，还有更新，说明路径上有 n+1 个点，也就是存在环，还有更新，说明环是负环
循环 n 次后, 所有的边u->v,权w满足三角不等式:dist[v]<=dist[u]+w

# 代码实现

LeetCode 787. Cheapest Flights Within K Stops (medium) (opens new window)

Bellman-Ford 算法

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        const int INF = 0x3f3f3f3f;
        vector<int> dist(n, INF); // 到起点的最短距离
        vector<int> backup(n); // 防止串联

        dist[src] = 0;
        for (int i = 0; i<= K; i++){ // 松弛K次
            backup.assign(dist.begin(), dist.end());
            for (auto &f: flights){ // 枚举所有边
                dist[f[1]] = min(dist[f[1]], backup[f[0]] + f[2]); // 更新最短路
            }
        }
        if (dist[dst] > INF /2) return -1;
        return dist[dst];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# spfa 算法

在各个方面都好于 Bellman-Ford 算法

但是不能求有边数限制的最短路

SPFA 算法是单源最短算法中限制最小的算法，只要没有负环，就可以用 SPFA 算法，一般的只要求最短路就不含有负环

SPFA 算法是对 Bellman-Ford 算法的优化

# 算法思路

n 个点，m 条边

对 Bellman-Ford 算法进行优化：

循环 n 次
- 遍历所有边u->v,权 w (松弛操作)
  - dist[v]=min(dist[v], dist[u]+w) ; 只有 dist[u]变小了，dist[v]才会变小

# spfa 算法步骤

queue <– 起始点
while queue 不为空
- t <– 队头
  - queue.pop()
- 用 t 更新所有出边 t –> v，权值为 w - queue <– v (若该点被更新过，则拿该点更新其他点) 时间复杂度: 一般：O(m) 最坏：O(nm)

# 场景

存在负权边，求单源最短路
spfa 也能解决权值为正的图的最短距离问题，且一般情况下比 Dijkstra 算法还好
spfa 算法更为通用，在求单源最短路的时候，我们可以先考虑 spfa 算法，如果数据被卡，再考虑实现别的单源最短路算法；一般笔面试题数据都不会被卡，OI，ACM 可能被卡

# 代码实现

LeetCode 743. Network Delay Time (medium) (opens new window)

spfa 算法

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        const int INF = 0x3f3f3f3f;
        vector<int> dist(N+1, INF); // 保存到起点的距离
        vector<bool> st(N+1, false); // 是否最短
        typedef pair<int, int> PII;
        unordered_map<int, vector<PII>> edges; // 邻接表

        queue<int> q;
        q.push(K);
        dist[K] = 0;
        st[K] = true; // 已经在队列中
        for (auto &t: times){
            edges[t[0]].push_back({t[1], t[2]});
        }

        while (!q.empty()){
            auto t = q.front();
            q.pop();
            st[t] = false;
            for (auto &e: edges[t]){
                int v = e.first, w = e.second;
                if (dist[v] > dist[t] + w){
                    dist[v] = dist[t] + w;
                    if (!st[v]){
                        q.push(v);
                        st[v] = true;
                    }
                }
            }
        }
        int ans = *max_element(dist.begin()+1, dist.end());
        return ans == INF ? -1: ans;
    }
};

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

# spfa 算法求负环

Acwing 852. spfa 判断负环

# 算法思路

增加cnt[N]来记录最短路的边数
当最短路的边数大于等于 n，可知经过的点大于等于 n+1
一共 n 个点，根据抽屉原理可知最短路存在负环

# 代码实现

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

typedef pair<int, int> PII;
unordered_map<int, vector<PII>> edges; // 邻接表
int n, m; // n个点，m条边
const int N = 2010;
int dist[N]; // 到起始点的最小距离
bool st[N];  // 在队列中是否存在
int cnt[N]; // 记录最短路的边数

bool spfa(){
    queue<int> q;
    for (int i = 1; i <=n; i++){ // 所有点入队列；负环可能存在在所有点出发的最短路上
        q.push(i);
        st[i] = true;
    }
    while (!q.empty()){
        int u = q.front();
        q.pop();
        st[u] = false; // 不在队列
        for (auto &e: edges[u]){
            int v = e.first, w = e.second;
            if (dist[v] > dist[u] + w){
                dist[v] = dist[u] + w; // 更新最短路 权值
                cnt[v] = cnt[u] + 1; // 更新经过的边数
                // 存在负环；边数>=n,经过的点>=n+1;根据抽屉原理得，最短路存在负环
                if (cnt[v] >= n) return true;
                if (!st[v]){
                    q.push(v);
                    st[v] = true;
                }
            }
        }
    }
    return false;
}
int main(){
    cin >> n >> m;
    while (m--){ // 构造图
        int u, v, w;
        cin >> u>> v>> w;
        edges[u].push_back({v, w});
    }
    if (spfa()) puts("Yes");
    else puts("No");
    return 0;
}

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

# Floyd 算法

多源汇最短路

for (k = 1; k<=n ; k++)
- for (i = 1; i<= n; i++)
  - for (j = 1; j<=n; j++)
    - d[i,j] = min(d[i,j], d[i,k]+d[k,j])

# 算法原理

floyd 算法是基于动态规划的

d[k, i, j] 表示从 i 出发，只经过 1~k 到达 j 点的最短距离

# 题目

AcWing 854. Floyd 求最短路

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

const int INF = 0x3f3f3f3f;
const int N = 210;
int n, m, k; // n个点，m条边，k次询问
int grid[N][N]; // 图的矩阵存储
int d[N][N]; // 最短距离

void floyd(){
    for (int k = 1; k <=n; k++)
        for (int i = 1; i<=n; i++)
            for (int j = 1; j<=n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main(){
    cin >> n >> m >> k;
    for (int i = 1; i <=n ; i++){ // 初始化邻接矩阵
        for (int j = 1; j<=n; j++){
            if (i == j) d[i][i] = 0; // 自己到自己距离0
            else d[i][j] = INF; // 到别的点距离正无穷
        }
    }
    int u, v, w;
    while (m--){ // m条边
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w); // 重边取最小
    }
    floyd(); // floyd计算多源最短路
    while (k--){ // k次询问
        cin >> u >> v;
        if (d[u][v] > INF/2) puts("impossible");
        // 由于存在负权边，所以比INF/2大，就是不可达
        else cout << d[u][v] << endl;
    }
    return 0;
}

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

← 0x61_图 0x64_最小生成树 →