图论-单源最短路径SPFA

定义

SPFA（Shortest Path Faster Algorithm）（队列优化）算法是求单源最短路径的一种算法，它还有一个重要的功能是判负环，在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。

流程

如果加权有向图G不存在负权回路，那么最短路径一定存在。用邻接表来存储图G，用数组f记录每个结点与起点之间的距离。
设立一个先进先出的队列用来保存可能给其出边所指向的节点带来优化的节点，优化时每次取出队首节点u，并且用u点当前与起点间的距离对自u点出边所指向的结点v进行松弛操作，如果v点与起点间的距离减小，就说明它可能给其出边所指向节点带来更新。若v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
队列为空，则说明没有节点可以给其他节点带来更新，整个松弛操作完成，已找到每个元素到达起点的最短路径

代码

题目地址：https://www.luogu.org/problemnew/show/P3371

#include <iostream>
#include <cstdio>
using namespace std;
int f[10001],a[10010],t,h,first[10001],next[500001],y[500001],z[500001];
int n,m,s;
int v[10001];
//变量含义：f[i]（i到起点的距离）,a[i]（队列）, first[i]（节点i的第一条出边）, next[i], 
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    int i,j,k,l,x;
    for (i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y[i],&z[i]);//读入数据 
        if (first[x]==0) first[x]=i;//邻接表存储 
        else
        {
            next[i]=first[x];
            first[x]=i;
        }
    }
    for (i=1;i<=n;++i) f[i]=2147483647;//初始化，将所有节点距起点的距离设为正无穷（一个非常大的数） 
    f[s]=0;//起点距离自己的距离为0 
    v[s]=1;//标记队列中的元素 
    a[++t]=s;//入队 
    while (h!=t)//如果队列非空，继续进行松弛操作 
    {
        h=(h+1)%10010;//出队，滚动队列（因为队列中每个元素都是唯一的，最多只有n个元素，没有队尾追上队头的可能性，该队列不可能溢出 ）
        v[a[h]]=0;//取消标记 
        for (i=first[a[h]];i!=0;i=next[i])//遍历所有与该节点a[h]相连的节点y[i] 
            if (f[y[i]]>f[a[h]]+z[i])//判断是否可以更新y[i]与起点间的距离
            {
                f[y[i]]=f[a[h]]+z[i];
                if (!v[y[i]])//如果y[i]得到了更新，则说明与y[i]出边所指向的节点拥有了得到更新的可能性，将y[i]入队 
                {
                    v[y[i]]=1;
                    t=(t+1)%10010;
                    a[t]=y[i];
                }
            }
    }//当队列为空，则说明没有节点可以给其他节点带来更新，整个松弛操作完成，已找到每个元素到达起点的最短路径 
    for (i=1;i<=n;++i) printf("%d ",f[i]);//输出 
}