最短路学习笔记

最短路学习笔记

最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由节点和路径组成的)中两节点之间的最短路径。

由于竞赛中不考查文中所述算法的证明,故本文不探讨与证明相关的内容,如有需要请自行查阅维基百科。

性质

  1. 对于边权为正的图,任意两个节点间的最短路不会重复经过某一个点或某一条边。
  2. 对于边权为正的图,任意两个节点间的最短路中的任意一条的节点数不会超过 nn ,边数不会超过 n1n - 1

确定起点的最短路径问题

这种问题也叫单源最短路问题,即已知起始节点,求最短路径的问题。在边权非负时适合使用 Dijkstra 算法,若边权为负时则适合使用 Bellman-ford 算法或者 SPFA 算法。

Dijkstra 算法

该算法的时间复杂度为 O(n2)O(n^2) ,使用堆优化后可达 O(mlogm)O(m \log m)

演示

Dijkstra 算法运行演示Dijkstra 算法运行演示

Dijkstra 算法每次取出未访问节点中距离最小的节点,并用该节点更新其他节点的距离。(在演示过程中访问过的节点会被标为红色)

实现

设起点为 11 ,终点为 nn

  1. 初始化 dist1=0dist_1 = 0 ,其余节点的 distdist 值为 \infty
  2. 找出一个未被标记的 distxdist_x 最小的节点 xx ,并将其加入集合 SS
  3. 扫描节点 xx 的所有出边 (u,v,w)(u, v, w) ,若 distv>distu+wdist_v > dist_u + w 则使用 distu+wdist_u + w 更新 distvdist_v
  4. 重复 2、3 两个步骤直到 US=\complement_U S = \emptyset

代码

题目链接:849. Dijkstra 求最短路 I - AcWing

#include <bits/stdc++.h>

using namespace std;

int n, m, x, y, z, g[505][505], dist[505];
bool st[505];

int diskstra() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for (int i = 1; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                t = j;
            }
        }
        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
        st[t] = true;
    }
    return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            g[i][j] = i == j ? 0 : 0x3f3f3f3f;
        }
    }
    for (int i = 1; i <= m; i++) {
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);
    }
    cout << diskstra() << endl;
    return 0;
}

堆优化的 Dijkstra 算法

使用堆优化的 Dijkstra 算法的时间复杂度为 O(mlogn)O(m \log n)

实现

使用堆代替找距离最近的点的操作即可。

由于 C++ STL 中的优先队列不支持删除元素的操作,所以队列中会有重复元素导致复杂度变为 O(mlogm)O(m \log m) ,但比手写堆要容易许多。

代码

题目链接:850. Dijkstra 求最短路 II

#include <bits/stdc++.h>

using namespace std;

int n, m, u, v, w, dist[200005];
vector<pair<int, int>> g[200005];
bool st[200005];

void dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push(make_pair(0, 1));
    while (!q.empty()) {
        auto t = q.top();
        q.pop();
        if (st[t.second]) continue;
        for (auto i : g[t.second]) {
            if (dist[i.first] > t.first + i.second) {
                dist[i.first] = t.first + i.second;
                q.push(make_pair(dist[i.first], i.first));
            }
        }
        st[tw] = true;
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
    }
    dijkstra();
    cout << (dist[n] == 0x3f3f3f3f ? -1 : dist[n]) << endl;
    return 0;
}

Bellman-Ford 算法

该算法的时间复杂度为 O(nm)O(nm) (对于存在最短路的图)。

实现

遍历所有边 (u,v,w)(u, v, w) ,若 distv>distu+wdist_v > dist_u + w 则使用 distu+wdist_u + w 更新 distvdist_v ,到没有更新操作发生时停止。

在没有负环的情况下最多遍历 nn 次所有边即可得到最短路。

判断负环

在第 nn 次遍历后如果仍能更新最短路径长度则可以判断存在负环。

代码

#include <bits/stdc++.h>

using namespace std;

struct node {
    int u, v, w;
} g[10005];

int n, m, k, dist[505];

void bellman_ford() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= m; j++) {
            dist[g[j].v] = min(dist[g[j].v], dist[g[j].u] + g[j].w);
        }
    }
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        cin >> g[i].u >> g[i].v >> g[i].w;
    }
    bellman_ford();
    if (dist[n] > 0x1f1f1f1f) {
        cout << "impossible" << endl;
    } else {
        cout << dist[n] << endl;
    }
    return 0;
}

SPFA 算法

SPFA 算法在国际上通称为「队列优化的 Bellman-Ford 算法」,仅在中国大陆地区称为 「SPFA 算法」(Shortest Path Fast Algorithm),在随机图上运行效率为 O(km)O(km)kk 是一个很小的常数),但在特殊构造的图上时间复杂度会退化为为 O(nm)O(nm)

实现

  1. 先初始化一个队列,并将起点入队。
  2. 取出队头 tt ,并扫描其所有出边 (u,v,w)(u, v, w) ,若 distv>distu+wdist_v > dist_u + w 则使用 distu+wdist_u + w 更新 distvdist_v ,并将 vv 入队。
  3. 重复上述步骤直到队列为空。

SPFA 判负环

在每次更新 dist[x] 的同时记录当前所走过的边数 cnt[x] = cnt[t] + 1 ,若 cnt[n] 大于等于 nn 则可以证明存在图中负环。

由于从 11 号点开始走不能保证走到所有的负环,因此需要将节点 1n1 \sim n 都入队进行查找。

卡 SPFA

  1. 生成一棵以起点为根的树,树高尽量高(比如 11 为起点时,可以令每个点 ii 的父亲在 max(i5,1)\max(i - 5, 1)i1i - 1 随机),边权随机,作为最短路径树,同时直接递推求出每个点的带权深度 did_i
  2. 对于剩下的边,端点 (a,b)(a, b) 随机,边权在 dbda|d_b - d_a|dbda+5|d_b - d_a| + 5 随机(如果是有向图则去掉绝对值符号, 55 可以换成其他较小的正数)

这样生成的图中,次短路的条数非常的多,而 SPFA 一旦错误地进入了次短路的分支,就会使得一整棵子树被赋错误的距离,从而在后期不得不重新更新。而由于边权接近,剪枝的效果会受到很大影响。

代码

SPFA 求最短路

题目:851. spfa求最短路 - AcWing

#include <bits/stdc++.h>

using namespace std;

int n, m, u, v, w, dist[100005];
vector<pair<int, int>> g[100005];

void spfa() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (auto i : g[t]) {
            if (dist[i.first] > dist[t] + i.second) {
                dist[i.first] = dist[t] + i.second;
                q.push(i.first);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
    }
    spfa();
    if (dist[n] == 0x3f3f3f3f) {
        cout << "impossible" << endl;
    } else {
        cout << dist[n] << endl;
    }
    return 0;
}

SPFA 判负环

题目:852. spfa判断负环 - AcWing

#include <bits/stdc++.h>

using namespace std;

int n, m, u, v, w, dist[100005], cnt[100005];
vector<pair<int, int>> g[100005];

bool spfa() {
    memset(dist, 0x3f, sizeof(dist));
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (auto i : g[t]) {
            if (dist[i.first] > dist[t] + i.second) {
                dist[i.first] = dist[t] + i.second;
                cnt[i.first] = cnt[t] + 1;
                if (cnt[i.first] >= n) return true;
                q.push(i.first);
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
    }
    cout << (spfa() ? "Yes" : "No") << endl;
    return 0;
}

确定终点的最短路径问题

与确定起点的问题相反,该问题是已知终结节点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

只需要反向存图然后再跑一遍单源最短路即可。

确定起点终点的最短路径问题

即已知起点和终点,求两节点之间的最短路径。

可以使用单源最短路算法并进行剪枝:在处理完到终点的最短路径后直接停止计算最短路。

全局最短路径问题

全局最短路径问题也叫多源最短路问题,可以求出图中所有的最短路径。适合使用 Floyd 算法,时间复杂度为 O(n3)O(n^3)

实现

fk,i,jf_{k, i, j} 表示经过若干个编号不超过 kk 的节点从 iijj 的最短路径长度。

容易发现,这个问题可以拆分为两个子问题:经过若干个编号不超过 k1k - 1 的节点从 iijj ,或者从 ii 经过 kk 再到 jj 。可以得出递推式:

fk,i,j=min(fk1,i,j,fk1,i,k+fk1,k,j)f_{k, i, j} = \min(f_{k - 1, i, j}, f_{k - 1, i, k} + f_{k - 1, k, j})

那么接下来考虑优化,在每次循环中只会用到 fk1f_{k - 1} 中的数据,可以使用滚动数组的思想压缩数组,所以递推式可以简化为:

fi,j=min(fi,j,fi,k+fk,j)f_{i, j} = \min(f_{i, j}, f_{i, k} + f_{k, j})

这样即可将空间复杂度优化到 O(n2)O(n^2)

代码

#include <bits/stdc++.h>

using namespace std;

int n, m, k, x, y, z, f[205][205];

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = i == j ? 0 : 0x3f3f3f3f3f;
        }
    }
    for (int i = 1; i <= m; i++) {
        cin >> x >> y >> z;
        f[x][y] = min(f[x][y], z);
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
    for (int i = 1; i <= k; i++) {
        cin >> x >> y;
        if (f[x][y] > 0x1fffffff) {
            cout << "impossible" << endl;
        } else {
            cout << f[x][y] << endl;
        }
    }
    return 0;
}

参考资料

  1. 最短路 - 图论 - OI Wiki
  2. 最短路问题 - 维基百科
  3. 戴克斯特拉算法 (Dijkstra 算法) - 维基百科
  4. Floyd-Warshall 算法 - 维基百科
  5. Bellman-ford 算法 - 维基百科
  6. 如何看待 SPFA 算法已死这种说法? - immortalCO 的回答 - 知乎
  7. 0x61 最短路,《算法竞赛进阶指南》,李煜东,2019 年 9 月。

文章头图来自《啊哈!算法》

最短路学习笔记
本文作者
宝硕
发布于
2021-08-12
更新于
2021-09-12
许可协议
喜欢这篇文章?为什么不考虑打赏一下作者呢?
爱发电
文章目录
  1. 性质
  2. 确定起点的最短路径问题
    1. Dijkstra 算法
      1. 演示
      2. 实现
      3. 代码
    2. 堆优化的 Dijkstra 算法
      1. 实现
      2. 代码
    3. Bellman-Ford 算法
      1. 实现
      2. 判断负环
      3. 代码
    4. SPFA 算法
      1. 实现
      2. SPFA 判负环
      3. 卡 SPFA
      4. 代码
  3. 确定终点的最短路径问题
  4. 确定起点终点的最短路径问题
  5. 全局最短路径问题
    1. 实现
    2. 代码
  6. 参考资料