最短路

两顶点之间什么时候存在最短路呢？

负权回路

存在负权回路不一定没有最短路，只要最短路不经过负权回路即可。

单源最短路

Dijkstra 算法

问题提出：给定一个带权有向图（可以有环） $G$ 与源点 $v$ ，求从 $v$ 到 $G$ 中其他顶点的最短路径。限定：各边上的权值大于或等于 $0$ 。

算法：基于贪心法的Dijkstra算法。注意该算法无法处理带有负权边的图。

朴素 Dijkstra 算法思想

说明：

$v_{0}$ 源点
辅助数组 $d i s t$ 。 $d i s t [i]$ 表示当前找到的 $v_{0} \to v_{i}$ 的最短路径的长度。
集合 $S$ 为已求得最短路径的终点集合

算法描述：

初始化 $S$ 和 $d i s t$
1. $S = \emptyset$
2. $d i s t [v_{0}] = 0$
3. $d i s t [i] = + \infty; i \in 1 \sim n & v_{i}! = v_{0}$
求出顶点 $v_{k}$ 并加入集合 $S$ ： $v_{k}$ 满足 $d i s t [k] = m i n {d i s t [i]}, i \in V - S$
更新与 $v_{k}$ 相连且不在 $S$ 中的顶点的最短路径长度： $d i s t [i] = m i n {d i s t [i], d i s t [k] + k \to i 边上的权值}, i \in V - S$
若 $S = V$ ，算法结束，否则重复 2、3

dijkstra图

模板习题

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出 $1$ 号点到 $n$ 号点的最短距离，如果无法从 $1$ 号点走到 $n$ 号点，则输出 $- 1$ 。

输入格式

第一行包含整数 $n$ 和 $m$ 。接下来 $m$ 行每行包含三个整数 $x, y, z$ 表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$ 。

输出格式

输出一个整数，表示 $1$ 号点到 $n$ 号点的最短距离。如果路径不存在，则输出 $- 1$ 。

数据范围

$1 \leq n \leq 500$ ,
$1 \leq m \leq 10^{5}$ , 图中涉及边长均不超过 10000。

输入样例

输出样例

参考代码

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int g[N][N]; // 思考：朴素版适用于稠密图，稠密图用什么存储？邻接矩阵
int s[N];
int dist[N];
int n, m;

int dijkstra(int st, int ed) { // st 源点 ed 需要输出最短路径长度的顶点
    memset(dist, 0x3f, sizeof dist); // 除远点外所有顶点的 dist 值为无穷大
    dist[st] = 0; // 源点的 dist 值为 0

    // for (int i = 1; i <= n; i++) { // s != v 即循环 n 遍求出源点到 n 个点的最短路径
    for (int i = 1; i < n; i++) { // s != v 即循环 n - 1 遍求出源点到 n - 1 个点的最短路径（源点已经求过了）
        int k = -1; // 求满足条件的顶点 k
        for (int j = 1; j <= n; j++) {
            if (!s[j] && (k == -1 || dist[j] < dist[k])) k = j;
        }
        s[k] = 1; // 顶点 k 加入 s

        for (int j = 1; j <= n; j++) { // 更新最短路径
            if(!s[j] && g[k][j] != INF) dist[j] = min(dist[j], dist[k] + g[k][j]);
        }
    }

    if (dist[ed] == INF) return -1;
    else return dist[ed];
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g); // 权值可能为 0 所以初始时选择无穷大

    for (int i = 1; i <= m; i++) {
        int a, b, w; cin >> a >> b >> w;
        g[a][b] = min(g[a][b], w); // 可能有重边
    }

    cout << dijkstra(1, n) << endl;

    return 0;
}

思考：如何记录最短路径？

cpp

int path[N];

int dijkstra(int st, int ed) {
    memset(dist, 0x3f, sizeof dist);
    dist[st] = 0;
    // 源点从 -1 走来
    path[st] = -1;

    for (int i = 1; i < n; i++) {
        int k = -1;
        for (int j = 1; j <= n; j++) {
            if (!s[j] && (k == -1 || dist[j] < dist[k])) k = j;
        }
        s[k] = 1;

        for (int j = 1; j <= n; j++) {
            if(!s[j] && g[k][j] != INF && dist[j] > dist[k] + g[k][j]) {
                dist[j] = dist[k] + g[k][j];
                path[j] = k; // 更新路径 j 从何处走来
            }
        }
    }

    if (dist[ed] == INF) return -1;

    for (int i = ed; i != -1; i = path[i]) {
        if (path[i] == -1) cout << i << endl;
        else cout << i << " <- ";
    }
    return dist[ed];
}

堆优化版 Dijkstra

使用小根堆将寻找顶点 $v_{k}$ 并更新出边的最短路径长度的时间复杂度降低到 $O (\log n)$ 。

思考：稀疏图使用邻接表存储。

cpp

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[N], w[N], ne[N], idx;
int s[N];
int dist[N];
int n, m;

void init() {
    memset(h, -1, sizeof h);
    idx= 0;
}

void add(int a, int b, int c) { // 有重边也没事 算法保证正确
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dijkstra(int st, int ed) {
    memset(dist, 0x3f, sizeof dist);
    dist[st] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({dist[st], st}); // 先存距离 pair默认按 first 排序

    while (heap.size()) {
        auto k = heap.top();
        heap.pop();

        int v = k.second, dis = k.first;

        if (s[v]) continue;
        s[v] = 1;

        for (int i = h[v]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dis + w[i]) {
                dist[j] = dis + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[ed] == INF) return -1;
    else return dist[ed];
}

int main() {
    init();

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c);
    }

    cout << dijkstra(1, n) << endl;

    return 0;
}

为什么 Dijkstra 算法不能处理负权边？

负权边

如上图 $v_{1} \to v_{3}$ 使用dijkstra算法求得的最短路是 $2$ 而实际上却是 $1 (v_{1} \to v_{2} \to v_{3})$ 。当我们第二次循环将 $v_{3}$ 加入 $S$ 后就算遇到了更短的路径也不会再更新 $v_{3}$ 的 $d i s t$ 值了

Bellman-Ford 算法

Bellman-Ford算法可以用来解决带有负权边的单源最短路问题，其基于动态规划思想，反复用已有的边更新最短路径的长度，该算法的核心思想便是松弛操作。

松弛：对于一条边 $(v_{i}, v_{j})$ ，记其权值为 $w$ ，比较 $d i s t [j]$ 和 $d i s t [i] + w$ 的大小关系；如果 $d i s t [j] > d i s t [i] + w$ 则使 $d i s t [j] = d i s t [i] + w$ 。上述操作即称为对边 $(v_{i}, v_{j})$ 的松弛。

算法思想：对图中每条边进行 $1$ 次松弛操作的时候，得到的实际上是至多经过 $0$ 个点的最短路径；对图中每条边进行 $2$ 次松弛操作的时候，得到的实际上是至多经过 $1$ 个点的最短路径......如果没有负权回路，那么任意两点间的最短路径至多经过 $n - 2$ 个顶点也就是 $n - 1$ 条边，因此经过 $n - 1$ 次松弛操作后应当可以求得最短路径。如果经过了 $n - 1$ 次松弛后还存在可以松弛的边，则说明图中存在负环！

提示：每一次松弛操作其实际意义就是再多考虑一条边之后能得到的最短路。

算法描述：

初始化：
1. $d i s t [i] = + \infty i \in 1 \sim n & v_{i}! = v_{0}$
2. $d i s t [v_{0}] = 0$
松弛：对所有边依次进行松弛操作，共 $n - 1$ 次

算法实现

cpp

// n 顶点数目
// m 边数目
// dist 记录源点到指定顶点的最小距离

// 因为算法只关注边，所以我们只存边
struct Edge {
    int u, v, w;
}edges[M]; // M 最大边数

void bellman_ford(int st, int ed) { // st 源点 ed 需要输出最短路的点
    memset(dist, 0x3f, sizeof dist);
    dist[st] = 0;

    for (int i = 1; i <= n; i++) { // 循环 n 遍是为了判断是否存在环
        bool flag = false;
        for (int j = 1; j <= m; j++) {
            if (dist[edges[j].v] > dist[edges[j].u] + edges[j].w) {
                dist[edges[j].v] = dist[edges[j].u] + edges[j].w;
                flag = true;
            }
        }

        if (!flag) break; // 本轮不存在距离更新，算法结束
        if (i == n) {
            cout << "图中存在负环" << endl;
            return ;
        }
    }

    // 特别注意这里的条件判断
    if (dist[ed] > 0x3f3f3f3f / 2) cout << "st 到 ed 的最短路不存在" << endl;
    else cout << "st -> ed 最短路为: " << dist[ed] << endl;
}

有边数限制的最短路问题

在某种特定的情况下必须使用Bellman-Ford算法！那就是所求最短路是有边数限制的。在这种情况下我们还需要注意一个点：求解最短路时需要借助备份数组。

串联：Bellman-Ford算法中的每次更新的意义是在多考虑 1 条边之后能得到的全局的最短路。而串联指的是一次更新之后考虑了不止一条边。
由于使用了松弛操作，某节点的当前最短路依赖于其所有入度的节点的最短路。假如在代码中使用dist[e.v]=min(dist[e.v],dist[e.u] + e.w);，我们无法保证dist[e.u]是否也在本次循环中被更新，如果被更新了，并且dist[e.v] > dist[e.u] + e.w，那么会造成当前节点在事实上“即考虑了一条从某个节点指向u的边，也考虑了u->v”，共两条边。而使用dist[e.v]=min(dist[e.v],last[e.u] + e.w);，可以保证u在dist更新后不影响对v的判定，因为后者使用last数组，保存着上一次循环中的dist的值。

问题：

给定一个 $n$ 个顶点 $m$ 条边的有向图，图中可能存在重边和自环，边权可以为负数。求从 $1$ 号顶点出发到达 $n$ 顶点且最多只能经过 $k$ 条边的最短距离，如果无法走到则输出impossible。

输入样例：

输出样例：

参考代码：

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 510, M = 10010;

struct Edge {
    int u, v, w;
} edges[M];

int n, m, k;
int dist[N];
int last[N]; // 备份数组

void bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < k; i++) {
        memcpy(last, dist, sizeof dist);
        for (int j = 0; j < m; j++) {
            auto e = edges[j];
            dist[e.v] = min(dist[e.v], last[e.u] + e.w);
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);
}

int main() {
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 0; i < m; i ++ ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }

    bellman_ford();

    return 0;
}

SPFA 算法

在Bellman-Ford算法中，对于最短路径长度未曾更新过的顶点，不必松弛由它出发的边，因此可以使用一个队列来避免这种无效的松弛：该队列在初始状态下只包含源点，仅当某个顶点的最短路径长度更新后，将该顶点加入队列中。算法在每一轮去队首的顶点，并松弛其所关联的边，直到队列为空。

算法实现

cpp

// vis 数组记录顶点 i 是否在队列中

void spfa(int st, int ed) {
    memset(dist, 0x3f, sizeof dist);
    dist[st] = 0;
   
    queue<int> q;
    q.push(st);
    vis[st] = 1;

    while (!q.empty()) {
        int k = q.front();
        q.pop();
        vis[k] = 0;

        for (int i = h[k]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[k] + w[i]) {
                dist[j] = dist[k] + w[i];
                if (!vis[j]) {
                    q.push(j);
                    vis[j] = 1;
                }
            }
        }
    }

    if (dist[ed] == 0x3f3f3f3f) cout << "不存在最短路径" << endl;
    else cout << dist[ed] << endl;
}

SPFA 求最短路

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出 $1$ 号点到 $n$ 号点的最短距离，如果无法从 $1$ 号点走到 $n$ 号点，则输出 impossible。数据保证不存在负权回路。

输入格式

第一行包含整数 $n$ 和 $m$ 。接下来 $m$ 行每行包含三个整数 $x, y, z$ ，表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$ 。

输出格式

输出一个整数，表示 $1$ 号点到 $n$ 号点的最短距离。如果路径不存在，则输出 impossible。

数据范围

$1 \leq n, m \leq 10^{5}$ ,
图中涉及边长绝对值均不超过 $10000$ 。

输入样例

输出样例

参考代码

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[N], w[N], ne[N], idx;
int vis[N];
int dist[N];
int n, m;

void init() {
    memset(h, -1, sizeof h);
    idx= 0;
}

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

void spfa(int st, int ed) {
    memset(dist, 0x3f, sizeof dist);
    dist[st] = 0;
   
    queue<int> q;
    q.push(st);
    vis[st] = 1;

    while (!q.empty()) {
        int k = q.front();
        q.pop();
        vis[k] = 0;

        for (int i = h[k]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[k] + w[i]) {
                dist[j] = dist[k] + w[i];
                if (!vis[j]) {
                    q.push(j);
                    vis[j] = 1;
                }
            }
        }
    }

    if (dist[ed] == INF) cout << "impossible" << endl;
    else cout << dist[ed] << endl;
}

int main() {
    init();

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c);
    }

    spfa(1, n);

    return 0;
}

SPFA 判断负环

Bellman-Ford算法也可以判断负环，为什么不用它呢？时间复杂度太高！

思路：
设cnt[u]表示从起点 st 到 u 的最短路径包含的边数，cnt[st] = 0。当执行更新 dist[v] = dist[u] + w 时，同样更新 cnt[v] = cnt[u] + 1.此时若满足 cnt[v] >= n，则图中有负环。若算法正常结束，则图中没有负环。

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[N], w[N], ne[N], idx;
int vis[N];
int dist[N];
int cnt[N]; // 记录最短路经过的边数
int n, m;

void init() {
    memset(h, -1, sizeof h);
    idx= 0;
}

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool spfa() {  
    queue<int> q;
   
    for (int i = 1; i <= n; i++) {
        q.push(i);
        vis[i] = 1;
    }

    while (!q.empty()) {
        int k = q.front();
        q.pop();
        vis[k] = 0;

        for (int i = h[k]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[k] + w[i]) {
                dist[j] = dist[k] + w[i];
                cnt[j] = cnt[k] + 1; // 从 k 到 j 经过边数 cnt[k] + 1
               
                if (cnt[j] >= n) return true; // 存在负环
                if (!vis[j]) {
                    q.push(j);
                    vis[j] = 1;
                }
            }
        }
    }

    return false;
}

int main() {
    init();

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c);
    }

    if (spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

多源最短路

Floyd-Warshall 算法

算法思想

floyd算法的本质是动态规划。设图 $G$ 的顶点数是 $n$ ， $d [k] [i] [j]$ 表示顶点 $i$ 到顶点 $j$ 只使用 $1 \sim k$ 作为中间节点集合时的最短路径长度。可知该集合可以划分为两部分

$i \to j$ 的最短路径中间不经过顶点 $k$ ： $d [k] [i] [j] = d [k - 1] [i] [j]$ 。
$i \to j$ 的最短路径中间经过顶点 $k$ ： $d [k] [i] [j] = d [k - 1] [i] [k] + d [k - 1] [k] [j]$ 。

状态计算： $d [k] [i] [j] = m i n (d [k - 1] [i] [j], d [k - 1] [i] [k] + d [k - 1] [j] [k]) (1 \leq i, j, k \leq n)$

优化降维： $d [i] [j] = m i n (d [i] [j], d [i] [k] + d [j] [k]) (1 \leq i, j, k \leq n)$

算法流程：

初始化（依题意）
1. $d [i] [j] = I N F$ （ $i$ $j$ 之间无边）
2. $d [i] [j] = w_{i, j}$ （ $i$ $j$ 之间有边）
3. $d [i] [i] = 0$
利用状态转移方程计算结果

cpp

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]);
            }
        }
    }
}

Floyd 求最短路

问题描述

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环，边权可能为负数。再给定 $k$ 个询问，每个询问包含两个整数 $x$ 和 $y$ ，表示查询从点 $x$ 到点 $y$ 的最短距离，如果路径不存在，则输出 impossible。数据保证图中不存在负权回路。

输入格式

第一行包含三个整数 $n, m, k$ 。接下来 $m$ 行，每行包含三个整数 $x, y, z$ ，表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$ 。接下来 $k$ 行，每行包含两个整数 $x, y$ ，表示询问点 $x$ 到点 $y$ 的最短距离。

输出格式

共 $k$ 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围

$1 \leq n \leq 200$

$1 \leq k \leq n^{2}$

$1 \leq m \leq 20000$

图中涉及边长绝对值均不超过 $10000$ 。

输入样例

输出样例

impossible
1

参考代码

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;
int d[N][N];
int n, m, q;

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 >> q;

    // 初始化邻接矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
        }
    }

    for (int i = 1; i <= m; i++) {
        int a, b, c; cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c); // 可能有重边，取边权最小的即可
    }

    floyd();

    while (q--) {
        int a, b; cin >> a >> b;
        // 注意这里的条件判断
        if (d[a][b] > INF / 2) cout << "impossible" << endl;
        else cout << d[a][b] << endl;
    }

    return 0;
}

最短路 ​

单源最短路 ​

Dijkstra 算法 ​

朴素 Dijkstra 算法思想 ​

模板习题 ​

输入格式 ​

输出格式 ​

数据范围 ​

输入样例 ​

输出样例 ​

参考代码 ​

堆优化版 Dijkstra ​

为什么 Dijkstra 算法不能处理负权边？ ​

Bellman-Ford 算法 ​

算法实现 ​

有边数限制的最短路问题 ​

SPFA 算法 ​

算法实现 ​

SPFA 求最短路 ​

输入格式 ​

输出格式 ​

数据范围 ​

输入样例 ​

输出样例 ​

参考代码 ​

SPFA 判断负环 ​

多源最短路 ​

Floyd-Warshall 算法 ​

算法思想 ​

Floyd 求最短路 ​

问题描述 ​

输入格式 ​

输出格式 ​

数据范围 ​

输入样例 ​

输出样例 ​

参考代码 ​

最短路

单源最短路

Dijkstra 算法

朴素 Dijkstra 算法思想

模板习题

输入格式

输出格式

数据范围

输入样例

输出样例

参考代码

堆优化版 Dijkstra

为什么 Dijkstra 算法不能处理负权边？

Bellman-Ford 算法

算法实现

有边数限制的最短路问题

SPFA 算法

算法实现

SPFA 求最短路

输入格式

输出格式

数据范围

输入样例

输出样例

参考代码

SPFA 判断负环

多源最短路

Floyd-Warshall 算法

算法思想

Floyd 求最短路

问题描述

输入格式

输出格式

数据范围

输入样例

输出样例

参考代码