SPFA最短路算法_spfa求最短路-程序员宅基地

技术标签：算法图论编程 SPFA

算法用途

这个算法，如其名：Shortest Path Fastest Algorithm，就是求最短路的算法。和 Dijkstra 一样，这是一个单源最短路算法。

算法原理

这个算法因为与贝尔曼福德（Bellman-Ford）算法比较相似，只是在它的算法的基础上进行了队列优化，因此也被嘲讽为“队列优化的贝尔曼福德”。

就是每次可以更新到一个节点的最短距离的时候，我们就更新它，并更新所有它能到达的子节点，直到没有节点需要被更新。

算法结果

算法运行结束后，将会得到一个处理好的数组 $d$ ，其中 $d [i]$ 代表从起点出发到节点 $i$ 的最短路长度。

算法实现

我们首先定义一个数组 $d$ ，代表我们选定的起点到其他各个点的距离最小值，将 $d$ 数组中除了起点以外的所有的元素都赋成INF（无限大）；
然后我们定义一个队列（先进先出），并将起点压入队列中，记录起点已经在队列中；
循环：取出一个节点（设为 $u$ ），枚举与之相连的节点（设为 $v$ ，并设 $线段 u v 的长度为 w$ ），如果：
- 发现 $d [u] + w < d [v]$ ，那么就更新 $d [v] = d [u] + w$ ，并且如果 $v$ 不在队列中，就将其加入队列，并记录 $v$ 点已经在队列中。
- 如果不满足 $d [u] + w < d [v]$ ，那么就什么也不做，继续取下一个 $v$ 。

请看图（啊啊啊啊啊这个破图我做了两天！！！要转载请注明出处！！！）。

SPFA GIF演示

例题

洛谷P3371 【模板】单源最短路径

P3371 【模板】单源最短路径

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。
接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例

输入样例#1：

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出样例#1：

0 2 4 3

说明

时空限制：

1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=15
对于40%的数据：N<=100，M<=10000
对于70%的数据：N<=1000，M<=100000
对于100%的数据：N<=10000，M<=500000

样例说明：

这个题就是模板题，直接打好 SPFA 就行了。

CPP源代码

#include<iostream>
#include<queue>
using namespace std;
int n,m,s;
#define MM 500005
#define MN 10005
#define INF 99999999
#define IINF 2147483647
struct node{
    int u,v,w,next;};
node edge[MM];
int head[MN];
int spfa[MN];
queue<int>q;
bool inq[MN];
void SPFA()
{
    
    q.push(s);
    inq[s]=true;
    for(int i=1;i<=n;i++) spfa[i]=INF;
    spfa[s]=0;
    while(!q.empty())
    {
    
        int u=q.front();q.pop();
        inq[u]=false;
        for(int i=head[u];i>0;i=edge[i].next)
        {
    
            int v=edge[i].v;
            int w=edge[i].w;
            if(spfa[v]>spfa[u]+w)
            {
    
                spfa[v]=spfa[u]+w;
                if(!inq[v])
                {
    
                    inq[v]=true;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
    
        int u,v,w;
        cin>>u>>v>>w;
        edge[i]=(node){
    u,v,w,head[u]};
        head[u]=i;
    }
    SPFA();
    for(int i=1;i<=n;i++)
    {
    
        if(spfa[i]==INF) spfa[i]=IINF;
        cout<<spfa[i]<<" "; 
    }
    return 0;
}

本文链接：https://blog.csdn.net/rentenglong2012/article/details/78483662

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

数据结构——顺序串（定义初始化、赋值、遍历、两串比较）_串的初始化-程序员宅基地

文章浏览阅读3.4k次，点赞8次，收藏47次。S;串的组成1length用length记录串的长度是为了减少后期的遍历串获取串长度的时间复杂度。如果不设置length的话，每一次获取字符串长度都需要一次循环，时间复杂度为O(n)，如果设置了length的话，给串新增字符的过程中就记录当前串的长度，未来需要串的长度的时候直接获取length就可以了，时间复杂度降低为O(1)。2chch是串里的字符串。......_串的初始化

Maven的dependency中无版本号的可能情况_android studio dependencies里没有版本信息-程序员宅基地

文章浏览阅读2.3k次。pom文件的依赖无版本号的可能原因_android studio dependencies里没有版本信息

Logstash：运用 jdbc_streaming 来丰富我们的数据_logstash jdbc_streaming-程序员宅基地

文章浏览阅读2.8k次，点赞4次，收藏7次。在IoT物联网时代，我们经常会遇到从传感器采集数据的情况。这些传感器，可以上传物联网数据，比如温度，湿度。通常这些传感器带有自己的ID，但是它并不具有像地理位置等这样的信息。当物联网数据传到我们的数据平台时，我们希望对采集上来的数据进行数据的丰富，比如我们对物联网的数据加上它所在的位置等信息，这将对我们的数据分析非常有用。这些需要丰富的数据通常会存放于一个关系数据库的表格中，比如MySQL的数据库..._logstash jdbc_streaming

工业数据分析技术与实战之入门——昆仑数据田春华培训听课记录_工业数据分析实战培训-程序员宅基地

文章浏览阅读512次。田老师发音不标准啊，好多词听好几遍，再关联上下文，连猜带蒙的才勉强能明白，不过有的也不一定对。记录以反复学习。视频链接：https://appgzdr0r6c3350.h5.xiaoeknow.com/v1/course/column/p_5e90181d2f5c2_Ut1xWLXN?type=3&share_user_id=u_5e91169429c27_G0xxVfLReS&share_type=2&scene=%E5%88%86%E4%BA%AB&access_en_工业数据分析实战培训

Cesium聚簇实现-kdbush原理-程序员宅基地

文章浏览阅读2.9k次，点赞4次，收藏16次。Cesium聚簇实现-kdbush源码剖析文章目录问题说明KDbush库的分块重排序算法说明KDbush库的查找范围点算法说明矩形框范围查找圆形范围查找上一篇文章通过调试发现Cesium实现点聚簇过程中一个bug，从中猜测其实现聚簇核心代码在kdbush类中，本文展开kdbush类查看它是如何实现点聚簇效果的。问题说明假设二维平面中有10个点，分别为ABCDEFGHIJ，如下图所示..._kdbush

linux 内核模块,Linux内核模块（一）-程序员宅基地

文章浏览阅读147次。Linux的模块化配置：将公版部分(常用的)编译到内核中，个性化部分(不常用的/驱动程序)独立出来编译成模块在用户空间中进行加载所需的模块到内核中[root@rhel6~]#ls/lib/modules/$(uname-r)/kernelarchcryptodriversfskernellibmmnetsoundarch..._config_vfat_fs