学习目标

贝尔曼福特算法、SPFA

 可以用来复习的B站视频：

1、https://www.bilibili.com/video/BV1RK4y1d7ct?p=3&vd_source=5c960e1ede940bc5cab8ed42c8bdc937

2、https://www.bilibili.com/video/BV18a4y1A7gv/?spm_id_from=333.999.0.0

 SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下时间复杂度和朴素 Bellman-Ford 相同，为 O(VE)。

贝尔曼-福特算法（Bellman-Ford algorithm）是一种用于计算单源最短路径的算法。它可以处理带有负权边的图，并且适用于有向图和无向图。

1. 初始化： 首先，将源节点的最短路径距离设为0，其他节点的距离设为无穷大。同时，设置一个数组来记录每个节点的前驱节点，初始化时所有前驱节点为空。

2. 迭代更新： 通过图中的所有边进行迭代。对于每一条边 (u, v)，检查是否通过节点 u 可以获得比当前已知的最短路径更短的路径到达节点 v。如果是，则更新节点 v 的最短路径距离为通过节点 u 到达节点 v 的路径长度，并将节点 v 的前驱节点设置为节点 u。

   这个过程就是“松弛操作”，它的目的是不断优化每个节点的最短路径估计。

3. 重复迭代： 重复上述迭代步骤，直到没有任何节点的最短路径距离发生变化。这意味着最短路径已经收敛，不再变化。

4. 检测负权回路： 如果在执行上述步骤的过程中，仍然存在某个节点的最短路径距离在迭代中发生变化，说明图中存在负权回路。这是因为负权回路允许我们无限次地降低路径长度。

5. 输出结果： 如果算法成功收敛，最终得到的每个节点的最短路径距离就是从源节点到该节点的最短路径长度。同时，通过前驱节点数组可以还原出最短路径的具体路径。

总体而言，这个算法的核心思想是通过迭代更新节点的最短路径估计，不断逼近最优解。这使得贝尔曼-福特算法可以处理包含负权边的情况，但也因为迭代的性质而导致时间复杂度较高。

下图只帮助回忆，图上看不出什么~

[小码君的太空基地]

#include<bits/stdc++.h>
using namespace std;

struct node{
    int from, to, len;  // 定义结构体node，表示边的起点、终点和权值
}a[10010];

int n, m, w, x, y, z, s, t;  // n为节点数，m为边数，w为权值，x、y、z为输入用的变量，s为源节点，t为目标节点
int d[10010], cnt;  // d数组存储起点到各节点的最短路径估计值，cnt为边的数量

void add(int from, int to, int len){
    // 定义函数add，用于向结构体数组a中添加边的信息
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].len = len;
    cnt++;
}

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

    for(int i = 1; i <= n; i++){
        d[i] = 1e9;  // 初始化起点到所有节点的最短路径估计值为无穷大
    }
    d[s] = 0;  // 起点到自身的最短路径为0
    for(int i = 0; i < m; i++){
        scanf("%d %d %d", &x, &y, &z);
        add(x, y, z);  // 添加边的信息到结构体数组a中
    }

    int from, to, len;
    for(int k = 0; k < n; k++){
        for(int i = 0; i < cnt; i++){
            from = a[i].from;
            to = a[i].to;
            len = a[i].len;
            // 松弛操作，更新目标节点的最短路径估计值  
            //估计值（estimation）指的是从源节点到某个节点的当前已知的最短路径的长度。
            if(d[to] > d[from] + len){
                d[to] = d[from] + len;
            }
        }
    }

    printf("%d\n", d[t]);  // 输出起点到目标节点的最短路径长度
    return 0;
}

//即使是重边，也可以松弛保存最短路径的 

SPFA算法

SPFA（Shortest Path Faster Algorithm）是一种用于解决单源最短路径问题的算法，它是贝尔曼-福特算法的一种优化。SPFA采用队列来管理待优化的节点，以提高算法效率。以下是SPFA算法的具体过程：

1. 初始化： 将源节点的最短路径距离设为0，其他节点的距离设为无穷大。同时，将源节点加入一个队列中，并标记为已加入队列。

2. SPFA主循环： 不断从队列中取出一个节点，并对其相邻的节点进行松弛操作。具体步骤如下：

   a. 从队列中取出一个节点u。

   b. 遍历节点u的所有相邻节点v。

   c. 如果通过节点u可以获得比当前已知的最短路径更短的路径到达节点v，即distance[v] > distance[u] + weight(u, v)，则更新节点v的最短路径距离为通过节点u到达节点v的路径长度，并将节点v加入队列。

   d. 如果节点v已经在队列中，不需要重复添加，避免不必要的重复操作。

   e. 重复上述步骤，直到队列为空。

3. 结束条件： 当队列为空时，表示没有节点可以继续进行松弛操作，算法结束。

4. 检测负权回路： 在SPFA的主循环中，如果某个节点进入队列的次数超过了n次，其中n是图中节点的数量，那么说明图中存在负权回路。

5. 输出结果： 如果算法成功结束，最终得到的每个节点的最短路径距离就是从源节点到该节点的最短路径长度。

总体而言，SPFA通过使用队列来管理待优化的节点，减少了不必要的重复操作，提高了算法效率。然而，仍然需要注意处理负权回路的情况，以避免算法无法终止。

[小码君的太空基地【SPFA】]

#include<bits/stdc++.h>
using namespace std;

int n, m, w, x, y, z, s, t;
int d[2505], vis[2505];
int a[2505][2505];

int main() {
    // 读取输入：节点数量 n，边数量 m，权值 w，起点 s，终点 t
    scanf("%d %d %d %d", &n, &m, &s, &t);
    // 初始化距离数组 d 和访问标记数组 vis
    for (int i = 1; i <= n; i++) {
        vis[i] = 0;      // 标记节点未被访问
        d[i] = 1e9;      // 将距离初始值设为无穷大
    }
    // 初始化邻接矩阵 a，表示节点之间的初始距离
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = 1e9;  // 将邻接矩阵初始值设为无穷大
        }
    }

    // 读取边的信息，并更新邻接矩阵
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &x, &y, &z);
        a[x][y] = z;       // 更新邻接矩阵，表示节点 x 到节点 y 的距离为 z
    }

    // 初始节点到自身的距离为0
    d[s] = 0;
    
    // 标记起点已经被访问
    vis[s] = 1;

    // 使用队列进行广度优先搜索
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;  // 重置节点 u 的访问状态

        // 遍历所有节点
        for (int i = 1; i <= n; i++) {
            // 如果通过当前节点 u 到达节点 i 的距离更短
            if (d[i] > d[u] + a[u][i]) {
                // 更新距离值
                d[i] = d[u] + a[u][i];

                // 如果节点 i 还未被访问，将其标记为已访问，并加入队列
                if (!vis[i]) {
                    vis[i] = 1;
                    q.push(i);
                }
            }
        }
    }

    // 输出起点到终点的最短距离
    cout << d[t];

    return 0;
}
/*
SPFA（Shortest Path Faster Algorithm）算法是对Bellman-Ford算法的一种优化。
Bellman-Ford算法是一种用于解决单源最短路径问题的算法，但它的时间复杂度相对较高，
为O(V*E)，其中V是节点数，E是边数。

SPFA通过一些优化策略，降低了在某些情况下的时间复杂度。具体而言，SPFA采用了队列
来辅助实现，它允许节点多次进入队列，但不一定每次都进行松弛操作，从而减少了冗余
的松弛操作。这种优化策略在一些图的情况下，特别是在稀疏图中，能够提升算法的效率。

总的来说，SPFA保留了Bellman-Ford算法的思想，但通过引入队列等机制，减少了一些不
必要的计算，从而提高了算法在实际应用中的性能。然而，需要注意的是，SPFA并不适用
于所有情况，因为在存在负权回路的图中，它可能无法正确终止。
*/

负权回路

[小码君的太空基地2]

 这个题要好好读懂题目，举例：意思就是能从A到B花3分钟，正常回来还是3分钟。但是如果有负权回路，那么回来的时间就可能为负数例如-2。那么就是题目表达的时空穿梭。

所以只要检测到负权回路，那么就能返回去。

#include<bits/stdc++.h>
using namespace std;
// 定义结构体表示图中的边
struct node {
    int from, to, len;
};
// 使用邻接表表示图
vector<node> v[505];
int n, m, w, x, y, z;
int d[510];
int main() {
    // 读取节点数、边数和特殊边数
    scanf("%d %d %d", &n, &m, &w);
    // 初始化距离数组，初始值为1e9
    for (int i = 2; i <= n; i++) {
        d[i] = 1e9;
    }
    // 读取普通边并构建邻接表
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &x, &y, &z);
        v[x].push_back((node){x, y, z});
        v[y].push_back((node){y, x, z});
    }
    // 读取特殊边并构建邻接表，注意特殊边的权值为负
    for (int i = 0; i < w; i++) {
        scanf("%d %d %d", &x, &y, &z);
        v[x].push_back((node){x, y, -z});
    }
    int from, to, len;
    // Bellman-Ford算法的主循环，迭代n次
    for (int k = 0; k < n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < v[i].size(); j++) {
                from = v[i][j].from, to = v[i][j].to, len = v[i][j].len;

                // 松弛操作
                if (d[to] > d[from] + len) {
                    d[to] = d[from] + len;

                    // 如果在第n次迭代中仍然有松弛操作，说明存在负环
                    if (k == n - 1) {
                        printf("YES\n");
                        return 0;
                    }
                }
            }
        }
    }
    // 循环结束后，如果没有在第n次迭代中检测到负环，输出"NO"
    printf("NO\n");
    return 0;
}

作业讲解视频：

链接：https://pan.baidu.com/s/1rC_GZ0crgDj6tMf-cciQlw?pwd=1mrg
提取码：1mrg