最短路问题 | 单源最短路 | 条条大路通罗马，有人生来在罗马

Dijkstra

算法特点

Dijkstra 是基于贪心的策略

简单最短路径问题：如果 i 到 j 的最短路经过 w，那么从 i 到 j 的最短距离一定为从 i 到 w 的最短距离加上从 w 到 j 的最短距离。

Dijkstra 不能处理带有负权边的情况

• 如果有负环，最短路径理论上为 -INF
• 但是如果此时规定最多经过 n 条边，此时带负环的最短路问题就可以求解。【bellman - ford 求解】

朴素版本

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 550;
int g[N][N];    // 用邻接矩阵存储图
int dist[N];    // 节点i到起点的最短距离
bool st[N]; // 判断节点i是否已经加入
int n, m;

int dijkstra()
{
    // 初始化最短距离
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    // 已选节点个数从1~n
    for(int i=1; i<=n; i++){
        int t = -1;
        // 节点从1到n开始遍历
        for(int j=1; j<=n; j++){
            // 选取还没加入 且 距离最短的节点
            if(!st[j] && (t==-1 || dist[j]<dist[t])) {
                t = j;
            }
        }
        // 加入该节点
        st[t] = true;
        
        // 更新最短距离
        for(int j=1; j<=n; j++){
            dist[j] = min(dist[j], dist[t]+g[t][j]);
        }
    }
    // int为4个字节
    // 如果dist[n]为无穷，说明无起点到n的最短路径
    if(dist[n] == 0x3f3f3f3f)   return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;
    // 因为图中可能存在重边和自环，且所有边权均为正值
    // 该情况下，最短路径一定不存在正环，所以需要将g[i][i]置为正无穷
    
    // 将邻接矩阵初始化为正无穷
    memset(g, 0x3f, sizeof(g));
    
    int x, y, z;
    for(int i=1; i<=m; i++){
        cin >> x >> y >> z;
        // 不是正环的情况下，更新g
        if(x != y) {
            // 重边只选取最小的
            g[x][y] = min(g[x][y], z);
        }
    }
    int res = dijkstra();
    cout << res << endl;
    return 0;
}

• dist[i]表示节点 i 到起点的最短距离。
• 初始置dist[i]=INF，dist[1]=0。
• 集合 s 用于存储当前已确定最短距离的点。
• 从1到 n 开始遍历（代表加入 s 的结点个数），找不在 s 中距离最短的点 t，更新最短距离dist[i]，然后吧节点 t 加入集合 s 中。

堆优化版

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

typedef pair<int, int> PII;
const int N = 200000;
int n, m;
int h[N], e[N], ne[N], idx;
int w[N];   // 记录边的权重
int dist[N];    // 到节点1的最短距离
bool st[N]; // 记录节点是否已加入集合

// 存在一条边，由a指向b，权重为c
void add(int a, int b, int c)
{
    // 边idx指向节点b
    e[idx] = b;
    w[idx] = c;
    // 边idx的下一条边是h[a]
    ne[idx] = h[a];
    // 节点a最新的一条边（表头）是idx
    h[a] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f3f3f3f, sizeof(dist));
    dist[1] = 0;
    // first: 到节点1的距离
    // second: 节点编号
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    // 将起始节点加入堆中
    heap.push({0, 1});
    while(heap.size() > 0) {
        // 取出到节点1距离最短的点
        auto t = heap.top();
        heap.pop();
        int d = t.first;
        int v = t.second;
        // 如果当前节点未加入集合
        if(st[v] == false) {
            st[v] = true;
            // 更新最短节点
            for(int i=h[v]; i!=-1; i=ne[i]) {
                int j = e[i];
                if(dist[j] > d+w[i]) {
                    dist[j] = d+w[i];
                    // 这里不更新堆中元素，直接插入堆
                    // 旧的一定比新的大，冗余后面会被pop出去
                    heap.push({dist[j], j});
                }
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f)   return -1;
    return dist[n];
}

int main()
{
    // 初始化
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for(int i=0; i<m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    cout << dijkstra() << endl;
    return 0;
}

Bellman - ford

算法特点

如果有负权边的话，最短路不一定存在

Bellman - ford 算法的核心思想是动态规划

状态定义：dist[i]表示经过 k 条边（该变量是隐含的），从源点到 i 的最短距离

状态计算：

• 第 k 次更新，从经历 k-1 条边的状态转移过来，利用三角不等式进行松弛操作：dist[v] = min(dist[v], dist[u] + w[u, v])

Bellman - ford 可以解决负环的问题

• 遍历 k 次代表最多经过 k 条边的最短路径。
• 如果总共有 n 给节点，第 n 次遍历仍在更新最短路径。根据抽屉原理，一定存在一条环，且该环一定是个负环。

有边数限制的最短路

题目描述

原题链接

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

程序代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 550, M = 10010;

// 定义边的数据类型
struct Edge
{
    int a, b, c;
} edges[M];

int n, m, k;
int dist[N];  // 从源点到i的最短路径长度（隐含经过了k条边）
int last[N];  // 上一状态的最短路径，经过k-1条边的最短路径长度

void bellman()
{
    // 初始化
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;  // 源点
    
    // 经过i条边
    for(int i = 1; i <= k; i++) {
        // 数组拷贝
        memcpy(last, dist, sizeof(dist));
        // 松弛操作
        for(int j = 0; j < m; j++) {
            auto e = edges[j];
            // 假设源点能到a，则源点到b的最短距离为min(dist[b], last[a]+c)
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    
    bellman();
    
    if(dist[n] > 0x3f3f3f3f / 2)  cout << "impossible" << endl;
    else  cout << dist[n] << endl;
    return 0;
}

SPFA

算法特点

spfa 本质上是对 bellman - ford 算法的一种队列优化

• Bellman - ford算法会遍历所有的边，但是有很多的边遍历了其实没有什么意义，只需要遍历那些到源点距离变小的点所连接的边即可
• 队列在 SPFA 算法中的作用是记录当前发生过更新的点，以便于进行松弛操作
• 这里使用一个st数组标记节点是否发生了更新，避免重复入队。

Dijkstra 算法 与 SPFA 算法的比较：

1. Dijkstra 算法中的 st 数组保存的是当前确定了到源点距离最小的点，且一旦确定了最小那么就不可逆了(不可标记为 true 后改变为false )
2. SPFA算法中的 st 数组仅仅只是表示的当前发生过更新的点，且 spfa 中的 st 数组可逆(可以在标记为 true 之后又标记为 false )。顺带一提的是 BFS 中的 st 数组记录的是当前已经被遍历过的点。
3. Dijkstra 算法里使用的是优先队列保存的是当前未确定最小距离的点，目的是快速的取出当前到源点距离最小的点；SPFA算法中使用的是队列(你也可以使用别的数据结构)，目的只是记录一下当前发生过更新的点。

spfa 求最短路

题目描述

原题链接

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

问题分析

程序代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 100100;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];    // 记录当前发生过更新的点
bool st[N]; // 标记节点是否发生了更新，避免重复入队

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

int spfa()
{
    // 初始化
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    
    // 记录当前发生过更新的点
    queue<int> q;
    // 判断与源点相邻的节点是否能更新
    q.push(1);
    st[1] = true;
    
    while(q.size() > 0) {
        int t = q.front();
        q.pop();
        
        // 相邻节点遍历，需要置回false
        st[t] = false;
        // 检查相邻节点是否能更新
        for(int i = h[t]; i != -1; i = ne[i]) {
            // 边：t-j
            int j = e[i];
            if(dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                // 如果节点 j 上一轮没更新过
                if( !st[j] ) {
                    // 加入邻接节点待更新的队列
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}

int main()
{
    // 初始化
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    
    int t = spfa();
    if(t == 0x3f3f3f3f)  cout << "impossible" << endl;
    else  cout << t << endl;
    return 0;
}

穷游？“穷”游

题目描述

贫穷的小 A 有一个梦想，就是到 t 国去一次穷游，但现实是残酷的。小 A 所在的世界一共有 n（n<=500）个国家，国家与国家之间总共有 E（E<=50000）条道路相连，第 i 个国家对于进入它的外国人都要收取 Bi 的费用，而小 A 家住在 s 国，他必须通过这些道路在各个国家之间中转最终到达 t 国（除非他运气够好可以直接从 s 国到达 t 国）。但是贫穷的小 A 只剩下 M（M<=100）元家底了，因此他必须精打细算旅途的费用，同时小 A 对于 t 国实在太向往了，因此他希望能够走最短的路尽快到达t国。这个问题难倒了小 A，现在他请你帮他算一算他到达t国的最短路径有多长。

输入

第一行输入T(T<=10)表示有T组数据。每组数据第一行输入n、E、s、t、M，分别表示小A所在世界的国家数、国家之间的总道路数、小A的国籍、小A向往的国家以及小A的家底；接下来一行输入n个正整数Bi，表示第i个国家收取的过路费（由于小A是s国人，因此s国不会收取，但t国会）；接下来输入E行每行三个正整数u(1<=u<=n)、v(1<=v<=n)、w，表示u国和v国之间存在着一条长度为w的无向边（可能有重边）。输入保证最终结果不会使int溢出。

输出

输出T行正整数，第i行表示第i组数据小A花费不超过M元到达t国的最短路。若小A无法到达t国，输出-1.

问题分析

这道题结合了 SPFA 求最短路和背包问题。

对于这道题，我们可以将最短路径看成背包装物品的价值，将小 A 的预算看成背包的容量。

状态定义：dist[i][j]表示从源节点出发，到达节点 i，预算为 j 的最短路径长度。

状态计算：

• 假设存在一条边(a, b)，边(a, b)的路径长度为c，点b的过路费为cost[b]，则dist[i][j] = min(dist[i][j], dist[b][j - cost[b]] + c)
• 找边的过程其实就是求最短路的过程，因此状态转移过程中，可以套用 SPFA 求最短路的方式，寻找边。

程序代码

#include <iostream>
#include <cstring>
#include <climits>
#include <queue>
using namespace std;

int T;
int n, m, s, t, money;
const int N = 550, E = 100010, M = 110, INF = 0x3f3f3f3f;
int dist[N][M];  // dist[i][j]：从源节点到i，费用为j的最短路径
int cost[N];  // 过路费
int h[N], w[E], e[E], ne[E], idx;
bool st[N]; // 标记节点是否发生了更新

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

int spfa()
{
    // 初始化
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <=money; j++) {
            if(i == s)  dist[i][j] = 0;
            else  dist[i][j] = INF;
        }
    }
    memset(st, false, sizeof(st));
    
    queue<int> q;
    // 需要判断与s相邻的节点是否能更新
    q.push(s);
    st[s] = true;
    
    while( !q.empty() ) {
        int top = q.front();
        q.pop();
        
        // 相邻节点遍历，需要置回false
        st[top] = false;
        // 检查相邻节点是否能更新
        for(int i = h[top]; i != -1; i = ne[i]) {
            // 边：top-j
            int j = e[i];
            for(int k = cost[j]; k <= money; k++) {
                if(dist[j][k] > dist[top][k - cost[j]] + w[i]) {
                    dist[j][k] = dist[top][k - cost[j]] + w[i];
                    // 如果节点 j 上一轮没更新过
                    if( !st[j] ) {
                        // 加入邻接节点待更新的队列
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }
    }
    
    int res = INF;
    for(int i = 0; i <= money; i++) {
        res = min(res, dist[t][i]);
    }
    
    if(res == INF)  res = -1;
    return res;
}

int main()
{
    cin >> T;
    while( T-- ) {
        cin >> n >> m >> s >> t >> money;
        for(int i = 1; i <= n; i++) {
            cin >> cost[i];
        }
        cost[s] = 0;
        int a, b, c;
        memset(h, -1, sizeof(h));
        idx = 0;
        for(int i = 0; i < m; i++) {
            cin >> a >> b >> c;
            add(a, b, c);
            add(b, a, c);
        }
        
        cout << spfa() << endl;
    }
    return 0;
}