JZTXT

最短路

发布时间 2023-12-23 07:16:22作者: RonChen

最短路是图论中最经典的模型之一，在生活中也有很多应用。例如，城市之间有许多高速公路相连接，想从一个地方去另一个地方，有很多种路径，如何选择一条最短路的路径就是最基本的最短路问题。有时候问题会更加复杂，加上别的限制条件，例如某些城市拥有服务区，连续开车达到一定的时间就必须要进服务区休息，或者是某些路段在特定的时间内会堵车，需要绕行等等，这需要更加灵活地使用最短路算法来解决这些问题。

除了解决给定图的最短路问题，最短路模型还可以解决许多看起来不是图的问题。如果解决一个问题的最佳方案的过程中涉及很多状态，这些状态是明确的且数量合适，而且状态之间可以转移，可以考虑建立图论模型，使用最短路算法求解。

单源最短路径

例：P3371 【模板】单源最短路径（弱化版）

题意：给定一个 \(n\) 个点 \(m\) 条边的有向图，以及一个起点 \(s\)，每条边长度（边权）给定，输出 \(s\) 到所有终点的最短路径长度（如无法到达则输出 \(2^{32}-1\)），所有边的长度均为非负整数，且保证最短路径长度不会超过 \(2^{32}-1\)

数据范围：\(1 \le n \le 10^4, 1 \le m \le 5 \times 10^5\)

分析：最简单的想法是，使用搜索来寻找所有可能的路径并比较它们的长度，选取最短的路径作为最短路。然而，由于可能的路径太多，时间复杂度是指数级别的，无法在规定时间内运行完毕。因此需要使用最短路算法，从起点开始尝试往外走，不断用已知点的最短路长度来更新其他点的最短路长度。

Dijkstra算法

用一个 \(dis\) 数组来记录到目前为止起点到各点的最短路径长度。

image

  1. 在初始时刻，先将整个 \(dis\) 数组设为 \(\infty\)
  2. 对于一条从 \(u\) 到 \(v\)，长度为 \(w\) 的边，如果 \(dis[u]+w<dis[v]\)，那么就可以将 \(dis[v]\) 的值变成 \(dis[u]+w\)，因为这代表着从 \(s\) 走到 \(u\) 经过这条边再走到 \(v\) 是一条未发现过的，且比原先的最优路径还要短的路径。这个操作称为松弛。假设 \(s=1\)，那么 \(dis[1]=0\) 且不会再变化。于是就可以用 \(1\) 号点的所有出边来进行松弛并将 \(1\) 标记，代表这个点的 \(dis\) 值将不再变化
  3. 可以发现 \(2\) 号点的 \(dis\) 值是当前未标记的点中最小的。由于从 \(1\) 走来的边已经全部完成松弛，且 \(dis[3]\) 和 \(dis[4]\) 都大于 \(dis[2]\)（这意味着从 \(3、4\) 号点走到 \(2\) 号点的边都无法成功松弛），所以此时的 \(dis[2]\) 就是从 \(1\) 到 \(2\) 的最短路。接着就可以用与 \(2\) 号点相连的所有边进行松弛并标记
  4. 同样地，发现 \(4\) 号点的 \(dis\) 是当前未标记的点中最小的，它的 \(dis\) 值不会再改变，接着用 \(4\) 号点进行松弛并标记
  5. 最后，用 \(3\) 号点进行松弛并标记得到最终结果

这种求最短路的方法是 Dijkstra 算法，其过程可以概括为：

  1. 将起始点的 \(dis\) 置为 \(0\)
  2. 选择当前未标记的点中 \(dis\) 值最小的一个
  3. 对该点的所有连边依次进行松弛操作
  4. 对该点进行标记
  5. 重复第二步至第四步，直到不存在一条从已标记点通往未标记点的连边
参考代码 
#include <cstdio>
#include <vector>
using namespace std;
const int N = 10005;
const int INF = 2147483647;
struct Edge {
    int to, w;
};
vector<Edge> g[N];
int dis[N];
bool vis[N];
int main()
{
    int n, m, s;
    scanf("%d%d%d", &n, &m, &s);
    while (m--) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});
    }   
    for (int i = 0; i <= n; i++) dis[i] = INF;
    dis[s] = 0;
    while (true) {
        int u = 0;
        for (int i = 1; i <= n; i++) 
            if (!vis[i] && dis[i] < dis[u]) u = i;
        if (u == 0) break;
        vis[u] = true;
        for (Edge e : g[u]) {
            int to = e.to, w = e.w;
            if (dis[u] + w < dis[to]) dis[to] = dis[u] + w;
        }
    }
    for (int i = 1; i <= n; i++) printf("%d%c", dis[i], i == n ? '\n' : ' ');
    return 0;
}

上述算法的时间复杂度是 \(O(n^2+m)\)，尽管这一复杂度能够本题，但并不够优秀

例：P4779 【模板】单源最短路径（标准版）

本题的 \(n \le 10^5, m \le 2 \times 10^5\)，因此用前面的算法无法通过本题了

需要对 Dijkstra 算法加一点优化：使用一个小根堆来维护 \(dis\) 最小的点。用一个结构体记录结点的编号 \(i\) 和 \(dis[i]\)，并以 \(dis[i]\) 为关键字排序。每次松弛成功时，将被松弛的边的终点和对应的 \(dis\) 值打包放入堆中，在需要寻找 \(dis\) 最小的点时将堆顶端的点取出，验证其是否已被标记即可。由于每一条边最多被入堆、出堆各一次，且堆内元素最多为 \(m\) 个，其时间复杂度为 \(O(m \log m)\)

参考代码 
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 100005;
const int INF = 2147483647;
struct Edge {
    int to, w;
};
vector<Edge> g[N];
int dis[N];
bool vis[N];
struct Node {
    int i, d;
};
struct NodeCmp {
    bool operator()(const Node& a, const Node& b) const {
        return a.d > b.d;
    }
};
priority_queue<Node, vector<Node>, NodeCmp> q;
int main()
{
    int n, m, s; scanf("%d%d%d", &n, &m, &s);
    while (m--) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});
    }
    for (int i = 1; i <= n; i++) dis[i] = INF;
    dis[s] = 0;
    q.push({s, 0});
    while (!q.empty()) {
        int u = q.top().i; q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (Edge e : g[u]) {
            int to = e.to, w = e.w;
            if (dis[u] + w < dis[to]) {
                dis[to] = dis[u] + w; q.push({to, dis[to]});
            }
        }
    }
    for (int i = 1; i <= n; i++) printf("%d%c", dis[i], i == n ? '\n' : ' ');
    return 0;
}

容易发现，当 \(m\) 和 \(n\) 同级时，采用堆优化会使得程序运行效率获得极大的提升；但如果 \(m\) 和 \(n^2\) 同级，那么使用堆优化之后复杂度变为 \(O(n^2 \log n^2)\)，反而劣于不加优化的 Dijkstra，在实际应用时，应当根据实际数据的范围来选择使用哪种算法

例：P1629 邮递员送信

题意：给定一张 \(n\) 个点 \(m\) 条边的有向图，邮递员从结点 \(1\) 出发，有 \(n-1\) 个快递，分别要送到结点 \(2\) 到 \(n\)，每次快递员只能携带一个快递出发并在送完后返回邮局。求邮递员走过的最少的路程。

数据范围：\(1 \le n \le 10^3, 1 \le m \le 10^5\)，保证任意两点间可相互到达

解题思路

由于快递员必须每次都要从 \(1\) 结点出发，到达结点 \(i\)，然后返回 \(1\)，因此就是求 \(1\) 到 \(i\) 的最短路，加上 \(i\) 到 \(1\) 的最短路。考虑到是有向图，从 \(1\) 到 \(i\) 的距离不一定等于从 \(i\) 到 \(1\) 的距离。计算从 \(1\) 到 \(i\) 的距离很简单，但如何求从其他结点到 \(1\) 的距离呢？而从某个点到 \(1\) 的路径，等价于从 \(1\) 开始，倒着沿路走。于是可以建立另外一个图，将读入的边起点和终点对调后存入这个新图中，从 \(1\) 开始计算到其他点的单源最短路径，得到的距离就是原图从其他点到起点的最短路径。一来一回加起来就是送货的最短路径

参考代码 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2005;
const int INF = 1e9;
int dis[N];
bool vis[N];
struct Edge {
    int to, w;
};
vector<Edge> g[N];
void update(int u) {
    vis[u] = true;
    for (Edge e : g[u]) {
        int to = e.to, w = e.w;
        dis[to] = min(dis[to], dis[u] + w);
    }
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    while (m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w}); 
        g[v + n].push_back({u + n, w});
    }
    for (int i = 0; i <= n * 2; i++) dis[i] = INF;
    dis[1] = 0;
    while (true) {
        int u = 0;
        for (int i = 1; i <= n; i++) 
            if (!vis[i] && dis[i] < dis[u]) u = i;
        if (u == 0) break;
        update(u);
    }
    dis[n + 1] = 0;
    while (true) {
        int u = 0;
        for (int i = n + 1; i <= n * 2; i++) 
            if (!vis[i] && dis[i] < dis[u]) u = i;
        if (u == 0) break;
        update(u);
    }
    int ans = 0;
    for (int i = 2; i <= n; i++) ans += dis[i] + dis[i + n];
    printf("%d\n", ans);
    return 0;
}

例：P4568 [JLOI2011] 飞行路线

解题思路

由于购买机票需要花费金钱，所以肯定不会重复乘坐多次同样的航线或者多次访问同一个城市。如果 \(k=0\)，本题就是最基础的最短路问题。但题目中提供了一些特殊情况（对有限条边设置为免费），可以使用分层图的方式，将图多复制 \(k\) 次，原编号为 \(i\) 的结点复制为编号 \(i+jn(1 \le j \le k)\) 的结点，然后对于原图存在的边，第 \(j\) 层和第 \(j+1\) 层的对应结点也需要连上，看起来就是相同结构的图上下堆叠起来，因此被称为分层图

image

从上面一层跳到下面一层就是乘坐免票的飞机，花费的代价是 \(0\)，这个过程是不可逆的，每乘坐一次免费航班就跳到下一层图中，因此上一层到下一层的边是单向的。从编号为 \(s\) 的结点开始，计算到其他点的单源最短路径。因为并不一定要坐满 \(k\) 次免费航班，所以查找所有编号 \(t+jn(0 \le j \le n)\) 的结点作为终点的最短路的值，找到的最小的值就是答案

参考代码 
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 110005;
const int INF = 1e9;
struct Edge {
    int to, w;
};
vector<Edge> g[N]; 
int dis[N];
bool vis[N];
struct Node {
    int i, d;
};
struct NodeCmp {
    bool operator()(const Node& a, const Node& b) {
        return a.d > b.d;
    }
};
priority_queue<Node, vector<Node>, NodeCmp> q;
int main()
{
    int n, m, k, s, t; 
    scanf("%d%d%d%d%d", &n, &m, &k, &s, &t);
    while (m--) {
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        g[a].push_back({b, c}); g[b].push_back({a, c});
        for (int i = 1; i <= k; i++) {
            int u = a + i * n, v = b + i * n;
            g[u].push_back({v, c}); g[v].push_back({u, c});
            g[u - n].push_back({v, 0}); g[v - n].push_back({u, 0});
        }
    }
    for (int i = 0; i < k * n + n; i++) dis[i] = INF;
    dis[s] = 0;
    q.push({s, 0});
    while (!q.empty()) {
        int u = q.top().i; q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (Edge e : g[u]) {
            int to = e.to, w = e.w;
            if (dis[u] + w < dis[to]) {
                dis[to] = dis[u] + w; q.push({to, dis[to]});
            }
        }
    }
    int ans = INF;
    for (int i = 0; i <= k; i++) ans = min(ans, dis[t + i * n]);
    printf("%d\n", ans);
    return 0;
}

小技巧：

  1. 某些边只能走有限的次数，可以将图复制多遍，成为分层图
  2. 给出若干个关键点，求其他点离这些关键点的距离，可以建立一个虚拟点，并使用长度为 \(0\) 的边将虚拟点和这些关键点连接
  3. 查找有向图中，所有结点到某个结点的最短路，可以将图反向建边
  4. 注意图中是否存在负环、自环、重边等情况