首页 > 编程语言 >C++ SPFA算法解析

C++ SPFA算法解析

时间：2024-08-22 16:39:32浏览次数：11  
标签：cnt cost int 算法 C++ vis SPFA edge

前言

将了解 C++ 求最短路中 SPFA 的算法

SPFA

SPFA的一些说明

SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，论文中的复杂度O(kE)，k为每个节点进入Queue的次数，且k一般<=2，但此处的复杂度证明是有问题的，其实SPFA的最坏情况应该是O(VE).!

引例：

输入格式

给出一个有向图，请输出从某一点出发到所有点的最短路径长度
三个整数 n， m， s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 m 行, 包含三个整数 u，v， w， u --> v， 长度为 w;

输出格式

输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 231 - 1;

输入样例 输出样例
4 6 1 0 2 4 3
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

此题的输入 数据范围 为 70% 即可通过

我们需要一个 数组 来记录 一个点 到 某个点 的最短距离， 我们可以定义一个 cost数组 来记录 权值

写好输入数据

我们的最大值可定义为 2e6 + 9 (即2000009), 不能到达则输出 231 - 1 (即2147483647）将它定义为 INF;

const int N = 2e6 + 9; // const常量，不可改变,数尽量大一些
const int INF = 2147483647;
int n, m, s, u, v, w;

void AddEdge() {} // 连边函数

signed main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= m; ++ i) {
        cin >> u >> v >> w;
        AddEdge(u, v, w); // 待会进行的连边所使用的函数
    }
}

连边

我们需要定义一个 结构体 Edge 然后进行连边操作

int cnt = 0, head[N];

struct Edge {
    int nxt, to, val; 
} edge[N];

void AddEdge(int from, int to, int val) {
    cnt++; // 记录操作次数
    edge[cnt].nxt = head[from];
    edge[cnt].to = to;
    edge[cnt].val = val;
    head[from] = cnt;    
}

SPFA函数的编写

主程序 main（续写） 中 连边后执行 SPFA 函数

signed main() {
    ……
    for (int i = 1; i <= m; ++ i) {
        cin >> u >> v >> w;
        AddEdge(u, v, w);
    }

    SPFA();
}

vis 记录节点是否 进/出 队列，cost 记录节点从 s 到 某个节点 的总共权值

int vis[N], cost[N];

在 SPFA 函数中， 我们要进行 vis 数组的 清零， 需用到 memset 函数来执行，让 cost[n] 里的各数值为 INF，即作为无穷大的数，当不可到达时，可直接输出 cost[i] (i为各个点），可到达时，使用 min（） 函数可求最短路径，将 cost[s] (即起点）的数值为 0， 因为它到它自己本身的距离为 0

void SPFA() {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++ i)
        cost[i] = INF;
    cost[s] = 0;
}

定义一个 队列 q，每次取 队头 执行 松弛操作，添加 起点

void SPFA() {
    ……
    cost[s] = 0;
    queue <int> q;
    q.push(s);
    vis[s] = 1；// 让起点 s 标记为 1， 代表已进入队列
}

当队列不为 空 时， 进行循环

void SPFA() {
    ……
    vis[s] = 1;
    while (!q.empty()) {
        int x = q.front(); // 获取队头数字
        q.pop(); // 弹出队头
        vis[x] = 0; // 队头已取出，此时 取出的队头 数字 的 vis[队头数字] 改为 0 代表 出队
    }
}

以下代码段为松弛操作（以便不懂的小伙伴）

if (cost[y] > cost[x] + edge[i].val) {
    cost[y] = cost[x] + edge[i].val;
        if (vis[y] == 0) {
            vis[y] = 1;
            q.push(y);
    }
}

队头已取出，此时 取出的队头 数字 的 vis[队头数字] 改为 0 代表 出队

void SPFA() {
    ……
    while (!q.empty()) {
        ……
        vis[x] = 0;
        for (int i = head[x]; i; i = edge[i].nxt) {
            int y = edge[i].to; // 代表为 i 时的 edge的 下一个指向
            if (cost[y] > cost[x] + edge[i].val) { // 如果 指向（未更改 原本存储） 的权值 大于 x 的权值 + 指向的权值
                cost[y] = cost[x] + edge[i].val; //进行 权值 的 更改
                if (vis[y] == 0) { //判断是否曾进入队列
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
    }
}

最后在主程序中进行 权值 的输出

signed main() {
    ……
    SPFA();
    for (int i = 1; i <= n; ++ i ) {
        cout << cost[i];
    }
}

最终代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 9; // const常量，不可改变
const int INF = 2147483647;
int n, m, s, u, v, w;
int cnt = 0, head[N], vis[N], cost[N];

struct Edge {
    int nxt, to, val;
} edge[N];
void AddEdge(int from, int to, int val) {
    cnt++;
    edge[cnt].nxt = head[from];
    edge[cnt].to = to;
    edge[cnt].val = val;
    head[from] = cnt;
}
void SPFA() {
    memset(vis, 0, sizeof(0));
    for (int i = 1; i <= n; ++ i)
        cost[i] = INF;
    cost[s] = 0;
    queue<int> q;
    q.push(s);
    vis[s] = 1;
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int i = head[x]; i; i = edge[i].nxt) {
            int y = edge[i].to;
            if (cost[y] > cost[x] + edge[i].val) {
                cost[y] = cost[x] + edge[i].val;
                if (vis[y] == 0) {
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
    }
}
signed main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= m; ++ i) {
        cin >> u >> v >> w;
        AddEdge(u, v, w);
    }
    SPFA();
    for (int i = 1; i <= n; ++ i) {
        cout << cost[i] << " ";
    }
}

SPFA的负环判断

洛谷负环判断模板题目：传送门

我将上述代码的变量 cnt 循环次数 改为 tim，创建了一个 cnt数组, 用来储存 每个数的入队次数

存储的是入队次数而不是松弛次数

int cnt[N];

题目部分要求

若 u >= 0，则表示存在一条从 u 至υ边权为 w 的边，还存在一条从υ至u 边权为 w 的边。
若 u < 0，则只表示存在一条从 u 至υ边权为 w 的边。

主程序 main 中的部分代码段应改为

for (int i = 1; i <= m; ++ i) {
    cin >> u >> v >> w;
    AddEdge(u, v, w);
    if (w >= 0) 
        AddEdge(v, u, w);
}

最终程序

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e6 + 9;
const int INF = 3e6 + 10;
int T;
int n, m, u, v, w, tim, head[N], vis[N], cost[N], cnt[N]; //cnt 换成 tim, 且创建 cnt 数组
struct Edge
{
    int nxt, to, val;
} edge[N];
// 清空函数: start
void Clear() {
    memset(edge, 0, sizeof(edge));
    tim = 0;
    memset(head, 0, sizeof(head));
    memset(vis, 0, sizeof(vis));
    memset(cost, INF, sizeof(cost));
    memset(cnt, 0, sizeof(cnt));
}
//清空函数: end
void AddEdge(int from, int to, int val) {
    tim++; //原本的cnt需改成tim，含义一致
    edge[tim].nxt = head[from];
    edge[tim].to = to;
    edge[tim].val = val;
    head[from] = tim;
}
bool SPFA() {
    memset(vis,0, sizeof(vis));
    for (int i = 1; i <= n; ++ i) cost[i] = INF;
    cost[1] = 0;
    queue<int> q;
    q.push(1); vis[1] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = false;
        for (int i = head[x]; i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (cost[v] > cost[x] + edge[i].val) {
                cost[v] = cost[x] + edge[i].val;
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                    cnt[v] ++; // 记录 edge[i].to 的次数
                    if (cnt[v] >= n) return true; // 如果 入队次数 已经 大于等于 n
                }
            }
        }
    }
    return false;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> T;
    while (T--) { //重复循环次数
        Clear(); //进行清空
        cin >> n >> m;
        for (int i = 1; i <= m; ++ i) {
            cin >> u >> v >> w;
            AddEdge(u, v, w);
            if (w >= 0) AddEdge(v, u, w); //更改的地方
        }
        cout << (SPFA() ? "YES" : "NO") << endl; //更改的地方
        }
}

因为进行多次 数组 的询问，我们要清空之前的数据

以上就是有关 SPFA 的知识点，感谢你能看到这里！ Cheer ！

相关练习：
洛谷 P3371：传送门

相关资料：
最短路相关算法复杂度比较

外部参考：
SPFA需要队列的原因
SPFA算法解析
链式前向星 相关知识_1
链式前向星 相关知识_2

标签：cnt,cost,int,算法,C++,vis,SPFA,edge
From： https://www.cnblogs.com/Mono-Awen/p/18374186

相关文章

  • 算法与数据结构——数据结构的分类
    数据结构的分类常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图，它们可以从“逻辑结构”和“物理结构”两个维度进行分类逻辑结构：线性与非线性逻辑结构揭示了数据元素之间的逻辑关系。在数组和链表中，数据按照一定顺序排列，体现了数据之间的线性关系；而在数中，数据从顶......
  • C++ 中几种类型转换
    C++中常用的类型除了隐式转换，还有显示转换，如：static_cast,dynamic_cast,const_cast,reinterpret_cast。其中隐式转换如常见的double、int、bool、float等类型之间的转换。显示转换的用法具体如下：一、static_cast：静态转换使用条件：（1）用于不同类型之间的转换，相当于隐式转换......
  • 【工程应用十一】基于PatchMatch算法的图像修复研究（inpaint）。
      这个东西是个非常古老的算法了，大概是2008年的东西，参考资料也有很多，不过基本上都是重复的。最近受一个朋友的需求，前后大概用了二十多天时间去研究，也有所成果，在这里简单的予以记录。  图像修复这个东西目前流行的基本都是用深度学习来弄了，而且深度学习的效果还是非常不错的（......
  • （算法）计算右侧⼩于当前元素的个数————＜分治-归并排序＞
    1.题⽬链接：315.计算右侧⼩于当前元素的个数2.题⽬描述：3.解法（归并排序）：算法思路：这⼀道题的解法与求数组中的逆序对的解法是类似的，但是这⼀道题要求的不是求总的个数，⽽是要返回⼀个数组，记录每⼀个元素的右边有多少个元素⽐⾃⼰⼩。但是在我们归并排序的过程中，元素的下......
  • （算法）翻转对————＜分治-归并排序＞
    1.题⽬链接：493.翻转对2.题⽬描述：题⽬解析：翻转对和逆序对的定义⼤同⼩异，逆序对是前⾯的数要⼤于后⾯的数。⽽翻转对是前⾯的⼀个数要⼤于后⾯某个数的两倍。因此，我们依旧可以⽤归并排序的思想来解决这个问题。3.解法（归并排序）：算法思路：⼤思路与求逆序对的思路⼀样，就......
  • 常用算法 -- 回溯算法
    1简介        回溯算法是一种基于试错思想的搜索算法，也是一种重要的编程技巧，常用于解决组合、排列、切割等问题。它通过不断尝试解决问题的每一步，一旦发现当前步骤不能得到有效的正确解，就会返回上一步或多步，并尝试其他可能的分步解决方案。这种策略使得回溯算法能够......
  • C++版的Minecraft
    非常垃圾的c++版Mc.#include<bits/stdc++.h>#include<windows.h>#include<conio.h>usingnamespacestd;typedefstructFrame{COORDposition[2];}Frame;voidColor(inta){//白if(a==0)SetConsoleTextAttribute(GetStdHandle(STD_O......
  • Dijkstra、Bellman_Ford、SPFA、Floyd算法复杂度比较
    说明Dijkstra：适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度O(E+VlgV)BellmanFord：适用于权值有负值的图的单源最短路径，并且能够检测负圈，复杂度O(VE)SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，论文中的复杂度O(kE)，k为每个节点进入Queue的次数，且k一般<=2，但此处......
  • 【C++】定义类型别名的三种方式及其优缺点：typedef，#define 和 using
    引言类型别名是一种给已存在的类型创建一个新名字的方式。这个新的名字（别名）和原类型在语义上是完全相等的，可以在任何原类型可以使用的地方使用。类型别名并不创建一个新的类型，只是为了提高代码的可读性和可维护性。在C++中，可以使用typedef，#define或者using来定义别名。每......
  • C++（typename）
    目录1.指定依赖于模板参数的类型2.定义嵌套依赖类型3.关键点：4.示例：5.需要注意的地方：总结：在C++中，typename是一个关键字，通常用于模板编程。它主要用于以下两种场景：1.指定依赖于模板参数的类型当你在模板中使用依赖于模板参数的类型时，C++编译器有时无法确定你是否指的是......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99