首页 > 其他分享 >spfa和bfs的区别

spfa和bfs的区别

时间:2022-10-27 15:34:33浏览次数:58  
标签:dist 区别 int st bfs spfa true

\(spfa\)和\(bfs\)的区别

\(spfa\)在形式上和\(bfs\)非常类似,不同的是\(bfs\)中一个点出了队列就不可能重新进入队列,但是\(spfa\)中一个点可能在出队列之后再次被放入队列,也就是一个点松弛过其它的点之后,过了一段时间可能本身被松弛,于是要再次用来松弛其它的点,这样反复迭代下去。

一、\(bfs\)算法模板

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
 
while (q.size()){
    int u = q.front();
    q.pop(); 

    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (!st[j]){
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

二、\(spfa\)算法模板

int spfa(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
 
    queue<int> q;
    q.push(1);
    st[1] = true;
 
    while (q.size()){
        auto u = q.front();
        q.pop();
 
        st[u] = false;
 
        for (int i = h[u]; ~i; i = ne[i]){
            int j = e[i];
            if (dist[j] > dist[u] + w[i]){
                dist[j] = dist[u] + w[i];
                // 如果队列中已存在j,则不需要将j重复插入
                if (!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    } 
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

在\(spfa\)中一个点的距离 可能被多次更新,因为有权值为 负数 的边,而\(Dijktra\),\(bfs\)所有边的 权值都非负,且每次更新其他点的距离的时候,都取的是当前未确定和起点距离的点中距离最小的点,所以当有其他路径通向这个点的时候不管是一条还是几条边距离一定都大于你选的这个边的距离,所以此时这个点到起点的距离就已经被确定不会改变了,而\(spfa\)允许存在负边,可能存在一条路径第一段权值较大,但是后几段距离是负数,就会更新\(dist\)了,所以在\(spfa\)算法中,在出队后将\(st[t]\)标记为\(false\),使得以后还可以入队来更新路径。

标签:dist,区别,int,st,bfs,spfa,true
From: https://www.cnblogs.com/littlehb/p/16832398.html

相关文章

  • STL库——push_back()与emplace_back()的区别
    相同点push_back()与emplace_back()都是往尾部添加一个元素不同点底层实现机制不同:push_back()向容器尾部添加元素时,首先会创建这个元素,然后再将这个元素拷贝或者移动......
  • sass和scss的区别
    首先注意,这里的sass和我们的scss是什么关系sass和scss其实是一样的css预处理语言,SCSS是Sass3引入新的语法,其后缀名是分别为.sass和.scss两种。SASS版本3.0之前的......
  • setInterval setTimeout区别
    区别:setTimeout只运行一次,也就是说设定的时间到后就触发运行指定代码,运行完后即结束;而setinterval是一直循环运行下去,即每到设定时间间隔就触发指定代码,要想停止,需要使用cl......
  • if 和三元表达式的区别
    在C语言层面除了写法以外没什么区别。inta=5;a==0?puts("x"):puts("z");if(a==0){puts("x");}else{puts("z");}在汇编语言层面上有一......
  • 关于for-in和for-of的区别
    1.循环数组区别一:forin和forof都可以循环数组,forin输出的是数组的index下标,而forof输出的是数组的每一项的值。constarr=['a','b','c','d']//for........
  • <semaphore.h> 和 <sys/sem.h> 的区别
    <sys/sem.h>为XSI(最初是UnixSystemV)信号量提供接口。这些不是基本POSIX标准的一部分(它们在XSI选项中,主要是为了传统的Unix兼容性),虽然它们还没有被认为是过时的/......
  • dependencies与dependencyManagement的区别
    dependencies与dependencyManagement的区别在我们项目顶层的POM文件中,我们会看到dependencyManagement元素。通过它元素来管理jar包的版本,让子项目中引用一个依赖而不用显......
  • GET和POST两种基本请求方法的区别
    GET和POST是HTTP请求的两种基本方法,要说它们的区别,接触过WEB开发的人都能说出一二。 最直观的区别就是GET把参数包含在URL中,POST通过requestbody传递参数。 你可能......
  • TCP与UDP的区别
    引言网络协议是每个前端工程师都必须要掌握的知识,TCP/IP中有两个具有代表性的传输层协议,分别是TCP和UDP,本文将介绍下这两者以及它们之间的区别。一、TCP/IP网络模型......
  • Spring中过滤器(Filter)和拦截器(Interceptor)的区别和联系
    在我们日常的开发中,我们经常会用到Filter和Interceptor。有时同一个功能。Filter可以做,Interceptor也可以做。有时就需要考虑使用哪一个比较好。这篇文章主要介绍一下,二者......