SPFA最短路算法

Shortest Path Fastest Algorithm （spfa） 单源最短路、存在负权边

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

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

int n,m;
int h[N],ne[N],e[N],w[N],idx;  //w[]权重
int dist[N];  //距离
bool st[N];   //记录当前点是不是在队列当中,防止队列中存储重复的点!!!!!!!!!!!!!!!!!!!!1

int spfa()
{
    //初始化
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;

    //用队列来存储待更新的点的下标
    queue<int> q;
    q.push(1);
    st[1]=true;

    while(q.size())
    {
        int t=q.front();
        q.pop();

        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }  
            }
        }
    }

    if(dist[n] == 0x3f3f3f3f)   return -1;
    return dist[n];

}