第三章：广搜深搜 - 最短路径问题 - 《y总基础算法笔记》

一:朴素的最短路径算法（Dijkstra算法）
二：堆优化的Dijkstra算法
三：Bellman-ford算法
四：SPFA算法
五：spfa判断负环
include
include
include
include

汇点就是终点
SPFA算法的时间复杂度一般情况是要比bellman-ford算法要好，经常因为边的条件被卡
如果正权边的情况，稀疏图就使用dijkstra算法
稠密图和稀疏图的区别，m和n^2一个级别就是稠密图

最短路算法难点就是建立图
spfa不能用于负环，但是bellman-ford算法可以

一:朴素的最短路径算法（Dijkstra算法）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int d[N]; // 每个点到起点的距离
int g[N][N]; // 有向图中边权值的记录
int n, m; 
bool st[N]; // s集合的记录，是否已经被选入最短点的集合
int Dijkstra()
{
    d[1] = 0; // 初始的1作为起点，距离是0
    for (int i = 0; i < n; i++)
    {
        int t = -1; // 这里为什么不直接取1作为起始，因为存在s集合，标记已经选完的点
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || d[t] > d[j])) // 没有选入s集合同时t==-1或者t这个点的距离不是距离起点最近的点
                t = j;
        if(t==n) break; // 优化，找到要找的，直接跳出
        st[t] = true; // 选出选取的点，直接放入s集合
        for (int j = 1; j <= n; j++)
        {
            d[j] = min(d[j], g[t][j] + d[t]); // 更新每个点到起点的距离
        }
    }
    if (d[n] == 0x3f3f3f3f) return -1; // n这个点出现无穷大，说明图不连续
    return d[n];
}
int main()
{
    memset(d, 0x3f, sizeof d); // 每个点距离起点的距离，包括1这个点，开始的时候，1还不是起点
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c); // 题目要求说了，有重复边，也就是一条边可能输入多次
    }
    cout << Dijkstra() << endl;
    return 0;
}

二：堆优化的Dijkstra算法

时间复杂度是N^2
时间复杂度是n
更新的边本质上是，时间复杂度可以理解为m

优化以后：

注意时间复杂度的变化：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII; // 使用的容器top得到的距离起点最近的点，需要知道这个点是什么，同时需要距离
const int N = 150010; // 注意题目要求的数据范围
int h[N], e[N], w[N], ne[N], idx; // 邻接表不同一点在于权重
bool st[N];
int d[N];
int n, m;
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; // 写权重的方式
}
int Dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;  // 小根堆，因为要找到最小距离的点
    d[1] = 0;
    heap.push({0, 1}); // 存入PII注意
    while (heap.size())
    {
        auto k = heap.top(); // 不能通过pop获得内容，同时可以使用auto接收
        heap.pop(); // 没有返回值
        int ver = k.second, dis = k.first; // 注意第一个数表示哪个点，第二个数代表距离起点的最小值是什么
        if (st[ver]) continue; // 因为使用的是堆，后面会把一些重复到一个点的距离加入到容器中，通过st实现过滤
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] > dis + w[i]) // 注意i 是idx，分辨清楚了，idx都是唯一的，5-10就是某一个点的，都固定好了
            {
                d[j] = dis + w[i];
                heap.push({d[j], j});
            }
        }
    }
    if (d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(d, 0x3f, sizeof d);
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << Dijkstra() << endl;
    return 0;
}

三：Bellman-ford算法

由于边数的限制，就是k的加入，只能使用这种算法
注意：如果能求出最短路，是没有负权回路的，例如下面 2—-3——4是权值为负数的回路，循环无穷次就是无穷负，也就是不一定存在最短路径

1—-2不存在存在

注意spfa算法使用的时候，一定要求不存在负环
注意下面需要把dist备份，备份的目的主要是串联，举个例子 1—-2距离为1，2——-3距离为1，1——-3距离，这个算法本质就是两层循环，第一层是k条边能到达的最短路径，第二层循环用更新的结点去更新新的距离，上面的例子，一开始，1点距离为0，2和3点的距离都是无穷，也就是i=0的时候，内部的循环更新的是所有到1点的距离，你看一下代码如果使用dist，那么由于串联的左右，第一次更新1—-2以后，到了2——3的时候，由于dist[2]已经不是无穷大，就会导致3被更新，但是我们已经知道最小距离是3，现在dist[3]变成了2就出问题了。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 10010;
int n, m, k; 
struct {
    int a, b, w;
} edge[M]; // 其实这个题感觉也可以实现dijkstra算法，邻接表和邻接矩阵好处自然是DFS和BFS可以
int d[N], backup[N];  // backup存在上面已经说过，本质外层循环一次就更新一层结点
int bellman_ford()
{
    d[1] = 0;
    for (int i = 0 ;i < k; i++)
    {
        memcpy(backup, d, sizeof d);
        for (int j = 0; j < m; j++)
        {
            int a = edge[j].a, b = edge[j].b, w = edge[j].w;
            d[b] = min(d[b], backup[a] + w); // 想清楚d是表示某个点到起点的距离，这个循环本质就是更新所有的边，但是是一层一层的更新
        }
    }
    if (d[n] > 0x3f3f3f3f / 2) return -1;
    return d[n];
}
int main()
{
    memset(d, 0x3f3f3f3f, sizeof d);
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        cin >> edge[i].a >> edge[i].b >> edge[i].w;
    }
    int t = bellman_ford();
    if (t == -1)
    {
        cout << "impossible" << endl;
    } else 
    {
        cout << t << endl;
    }
    return 0;
}

四：SPFA算法

优化点如下：

bellman-ford算法暴力，只有dis[a]变小才会导致dis[b]变小

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int h[N], ne[N], e[N], w[N], idx;
int n, m;
int d[N];
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int spfa()
{
    d[1] = 0;
    queue<int> q;
    q.push(1);
    while (q.size())
    {
        auto k  = q.front();
        q.pop();
        for (int i = h[k]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] > d[k] + w[i])
            {
                d[j]  = d[k] + w[i];
                q.push(j); // 题目要求说又重复边，这里可能重复推入多个相同的边，可以通过加入st数组，只要是某个点加入过queue就行，只需要更新d就可以了，不用重复加入了
                // 本质就是之加入d[j]变小的那个点，加入队列以后，就会导致其他的点减小，不减小的不用管了
            }
        }
    }
    if (d[n] == 0x3f3f3f3f) return -1; // 因为不是每条边的遍历，只进行dist变小的点的遍历，所以不用考虑上面导致最大值，不断变小的情况，不用/2
    return d[n];
}
int main()
{
    ios::sync_with_stdio(false);
    memset(h, -1, sizeof h);
    memset(d, 0x3f, sizeof d);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = spfa();
    if (t == -1)
    {
        cout << "impossible" << endl;
    } else {
        cout << t << endl;
    }
    return 0;
}

五：spfa判断负环

需要加一个数组，维护最短路径是几条边

判断负环的原理也很简单，根据抽屉原理，n条边一定是n+1个点，一定是两个点重复，又因为上面只有满足才更新距离和cnt，这样就代表中间存在了负环。

就是在spfa的基本算法上加上几句话，下面注释那几句 ```cpp
include
include
include
include

using namespace std;

const int N = 100010;

int h[N], e[N], ne[N], w[N], idx; int n, m; int d[N], cnt[N];

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

int spfa() { memset(d, 0x3f, sizeof d); d[1] = 0; queue q; for (int i = 1; i <= n; i++) // 如果queue从1出发，很有可能找不出这个负环，很有可能到不了负环，所以需要全都放入队列 { q.push(i); } while (q.size()) { auto k = q.front(); q.pop(); for (int i = h[k]; i != -1; i = ne[i]) { int j = e[i]; if (d[j] > d[k] + w[i]) { d[j] = d[k] + w[i]; cnt[j] = cnt[k] + 1; // 更新距离的时候，同时更新边的数目 if (cnt[j] >= n) return true; q.push(j); } } } return false; }

int main() { ios::sync_with_stdio(false); 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); }

if (spfa())
{
    cout << "Yes" << endl;
} else 
{
    cout << "No" << endl;
}
return 0;

} ```