最短路问题从入门到负权最短路

一，BFS层次最短路

/*题目描述
题目描述
给出一个 N 个顶点 M 条边的无向无权图，顶点编号为 1∼N。
问从顶点 1 开始，到其他每个点的最短路有几条。
输入格式
第一行包含 2 个正整数 N,M，为图的顶点数与边数。
接下来 M 行，每行 2 个正整数 x,y，表示有一条连接顶点 x 和顶点 y 的边，请注意可能有自环与重边。
输出格式
共 N 行，每行一个非负整数，第 i 行输出从顶点 1 到顶点 i 有多少条不同的最短路，由于答案有可能会很大，
你只需要输出 ans mod 100003 后的结果即可。如果无法到达顶点 i 则输出 0。
https://www.luogu.com.cn/problem/P1144
https://vjudge.net/contest/737432#problem/D
*/

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
const long long mod = 1e5 + 3;

int n, m, s, dis[maxn];
long long cnt[maxn];
vector<int> g[maxn];

void bfs() {
    queue<int> que;
    fill(dis+1, dis+n+1, -1);
    dis[1] = 0;
    cnt[1] = 1;
    que.push(1);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto v : g[u]) {
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                cnt[v] = cnt[u];    // u = 3
                que.push(v);
            }
            else if (dis[v] == dis[u] + 1)  // u == 7
                cnt[v] = (cnt[v] + cnt[u]) % mod;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, u, v; i < m; i++) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs();
    for (int i = 1; i <= n; i++)
        printf("%lld\n", cnt[i]);
    return 0;
}

我认为BFS层次最短路最关键的特征有两个，首先是层次（通过队列先入先出的特征来实现），其次是边权为1，如果边权不是1的话那么同样走一步就会有的步伐大有的步伐小，根本无法判断那条路最短。

二，dijkstra单源最短路

/*题目描述
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 n,m,s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 m 行每行包含三个整数 u,v,w，表示一条 u→v 的，长度为 w 的边。
输出格式
输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2^31?1。
https://www.luogu.com.cn/problem/P4779
https://vjudge.net/contest/737432#problem/B
*/

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, inf = INT_MAX;
int n, m, s, dis[maxn];
bool vis[maxn];
struct Edge {
    int v, w;
};
vector<Edge> edge[maxn];

struct Node {
    int u, dist;
    bool operator < (const Node& b) const {
        return dist > b.dist;  // 小根堆（优先队列默认是大根堆，这里取反）
    }
};
priority_queue<Node> quenode;

void dijkstra(int s) {
    fill(dis + 1, dis + n + 1, inf);
    dis[s] = 0;
    quenode.push({ s, 0 });
    while (!quenode.empty()) {
        int u = quenode.top().u;
        quenode.pop();
        if (!vis[u]) {  // 已经处理过的节点直接跳过
            vis[u] = true;
            for (auto& e : edge[u]) {
                int v = e.v;
                int w = e.w;
                // 松弛操作：如果通过u到v的路径更短，则更新
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    quenode.push({ v, dis[v] });
                }
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0, u, v, w; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        edge[u].push_back({ v, w });
    }
    dijkstra(s);
    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    return 0;
}

反观dijstra在这方面就有优异的表现，dijstra算法通过根据边权进行提前排序，以及优先队列存储被更新过的新路径进行高效且简单地求出单源最短路，但可以说正是因为dijstra的高效，它无法处理负权边的问题，这是因为dijstra高效在 vis 数组会把一些节点视作“永久节点”，即不会出现更短的路径通向该节点因此“永久节点”不会再被更新，但是负权边的存在使得“永久节点”不再永久，有可能会出现比通向该节点的“最短边”更短的边，另外，如果一个环的权值之和是负的那么通过这个环的“代价”将变成“动力”，因此会出现死循环。

三，Floyd算法求多源最短路

/*题目描述
给出一张由 n 个点 m 条边组成的无向图。
求出所有点对 (i,j) 之间的最短路径。
输入格式
第一行为两个整数 n,m，分别代表点的个数和边的条数。
接下来 m 行，每行三个整数 u,v,w，代表 u,v 之间存在一条边权为 w 的边。
输出格式
输出 n 行每行 n 个整数。
第 i 行的第 j 个整数代表从 i 到 j 的最短路径。
https://www.luogu.com.cn/problem/B3647
*/

#include <bits/stdc++.h>
using namespace std;
int n, m, dis[105][105];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dis[i][j] = (i == j) ? 0 : 1e9;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        dis[u][v] = dis[v][u] = min(dis[u][v], w);
    }
    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]);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++)
            cout << dis[i][j] << " ";
        cout << endl;
    }
    return 0;
}

其实 Floyd 算法更像是动态规划，逻辑上很好理解，dis[i][j] 代表了从 i 到 j 的最短路，然后分类讨论途径第 k 条路径的最短路，但是我更想介绍的是Floyd算法的一类衍生问题，传递闭包。

附：传递闭包

/*题目描述
https://www.luogu.com.cn/problem/B3611
*/
#include <bits/stdc++.h>
using namespace std;
int n, a;
bitset<100> f[100];
// f[i][j] = 1/0 目前能不能从i到j
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &a);
            if (a)
                f[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++) // 经过编号 [0,i] 的点
        for (int j = 0; j < n; j++) // 对于顶点j来说
            if (f[j][i])
                f[j] |= f[i];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            printf("%d ", (int)f[i][j]);
        putchar('\n');
    }
    return 0;
}

简单来说传递闭包问题就是判断任意两个节点之间是否可以到达，与Floyd相同的地方在于都是多源的问题，不同点在于数组只会存储 0 或 1 ，所以我们可以用bitset优化一下，大约省了几十倍的空间，最核心的段落就是if (f[j][i]) f[j] |= f[i]; 这一判断，当发现 i 与 j 可到达时，i 所能到达的节点 j 也能到达，反之亦然。

四，bellman-ford算法

/*题目描述
https://www.luogu.com.cn/problem/P3385
*/
#include <bits/stdc++.h>
using namespace std;
// bellman-ford判负环
const int maxn = 2e3 + 5, maxm = 3e3 + 5, inf = (1 << 29);

int T, n, m, dis[maxn];
struct Edge {
    int u, v, w;
} e[maxm];

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        dis[1] = 0;
        fill(dis + 2, dis + n + 1, inf);
        for (int i = 0; i < m; i++)
            scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        // bellman-ford
        int c = 0;
        for (int i = 1; i <= 2 * n; i++) {
            for (int j = 0; j < m; j++) {
                int u = e[j].u;
                int v = e[j].v;
                int w = e[j].w;
                if (dis[u] < inf && dis[v] > dis[u] + w)
                    c = i, dis[v] = dis[u] + w;
                if (w >= 0 && dis[v] < inf && dis[u] > dis[v] + w)
                    c = i, dis[u] = dis[v] + w;
            }
            if (c != i)
                break;
        }
        puts(c == 2 * n ? "YES" : "NO");
    }
    return 0;
}

理论上来说，同为单源最短路算法，所有dijkstra算法能用的题目bellman-ford也能用，可以理解为一个更容易实现，一个更全面，以上是一个一般的bellman-ford算法，我一般不用，以下是一个队列优化后的bellman-ford算法，它还有一个响当当的名字（SPFA）。

附：SPFA

#include <bits/stdc++.h>
using namespace std;
// SPFA判负环
const int maxn = 2e3 + 5, maxm = 3e3 + 5, inf = (1<<29);

int T, n, m, dis[maxn], cnt[maxn];
bool inq[maxn];
struct Edge {
    int v, w;
};
vector<Edge> g[maxn];

void init() {
    for (int i = 1; i <= n; i++)
        g[i].clear();
}

bool spfa() {
    queue<int> que;
    dis[1] = cnt[1] = 0;
    fill(dis + 2, dis + n + 1, inf);
    que.push(1);
    fill(inq + 1, inq + n + 1, false);
    inq[1] = true;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        inq[u] = false;
        for (auto &g : g[u]) {
            if (dis[g.v] > dis[u] + g.w) {
                dis[g.v] = dis[u] + g.w;
                cnt[g.v] = cnt[u] + 1;
                if (cnt[g.v] >= n)
                    return true;
                if (!inq[g.v])
                    inq[g.v] = true, que.push(g.v);
            }
        }
    }
    return false;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        init();
        for (int i = 0, u, v, w; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            g[u].push_back({v, w});
            if (w >= 0)
                g[v].push_back({u, w});
        }
        puts(spfa() ? "YES" : "NO");
    }
    return 0;
}

 bellman-ford 算法和SPFA算法的核心都是“松弛”（意思就是变短），简单点来说就是，只有一个终端节点（队头节点）的最短距离被更新（松弛）过之后，它将作为开始节点入队。因为在一个有 n 个顶点的图中，最短路径最多包含 n-1 条边（否则必然存在环），所以我们只需要开一个数组 cnt 记录每条路径经过几个节点，当 cnt[i] 大于等于 n 时说明存在环，而又由于我们算的是最短路径，正常情况下来讲算最短路是不可能算出环的，如果出现环那就一定是负环，详见代码。