SPFA最短短絡帯負重み辺の----粗理解

SPFA(Shortest Path Faster Algorithm)は、Bellman−Fordアルゴリズムのキュー実装であり、不要な冗長計算を低減する.
アルゴリズムの概略フローは、1つのキューでメンテナンスされます.最初はソースをキューに追加します.キューから要素を取り出し、隣接するすべての点を緩和するたびに、隣接する点の緩和が成功すると、それをキューに入れます.キューが空のときにアルゴリズムが終了するまで.
このアルゴリズムは、簡単に言えばキュー最適化のbellman-fordであり、各ポイントが更新回数が多すぎないという特徴を利用して発明されたこのアルゴリズムである
SPFA-Shortest Path Faster Algorithmは、O(kE)の時間的複雑さの中でソース点から他のすべての点への最短経路を求めることができ、負のエッジを処理することができる.SPFAの実現はDijkstraやBellmanよりもフォードはもっと簡単だ
SPFAは負のエッジを扱うことができる
定理:最短経路が存在する限り,上記SPFAアルゴリズムは必ず最小値を求めることができる.
証明:
点をキューの最後に入れるたびに,緩和操作によって達成される.すなわち、最適化のたびに、ある点vの最短経路推定値d[v]が小さくなる.したがって、アルゴリズムの実行はdをますます小さくする.図に負の重み回路が存在しないと仮定するため,各ノードに最短パス値がある.したがって,アルゴリズムは無限に実行されず,d値が徐々に小さくなり,最短経路値に達するまでアルゴリズムが終了すると,このときの最短経路推定値がノードに対応する最短経路値となる.
所望の時間複雑度O(ke)は、kがすべての頂点のキューに入る平均回数であり、kが一般的に2以下であることを証明することができる.
負のループの有無を判断する:
あるポイントがキューに入る回数がN回を超えると負ループが存在する(SPFAは負ループ付きの図を処理できない)

/*********************************************/
//  d          dis  ，     i       
//  c         i     
//  vis          
//            ，w     
/*********************************************/
bool spfa_bfs(int s) // s     
{
    queue <int> q; //       
    memset(d,0x3f,sizeof(d));  
    memset(c,0,sizeof(c));
    memset(vis,0,sizeof(vis));
    q.push(s);
    vis[s]=1;
    c[s]=1;
    d[s]=0;
    //    vis    ，            
    while(!q.empty())
    {
        int x;
        x=q.front();
        q.pop();
        vis[x]=0;
        //      ，      
        for(int k=f[x]; k!=0; k=nnext[k]) //    x    
        {
            int y=v[k];
            if( d[x]+w[k] < d[y]) //      
            {
                d[y]=d[x]+w[k];  //  
                if(!vis[y])  //  y             
                {
                    vis[y]=1;    //  
                    c[y]++;      //    
                    q.push(y);   //  
                    if(c[y]>NN)  //        ，     
                        return false;
                }
            }
        }
    }
    return true;
}

練習のテーマを与える.
クリックしてリンクを開く
本人ACコード:ご参考までに、間違っているところをご指摘ください
大まかな考え方:
隣接するテーブルの保存図を配列でシミュレートし、テンプレートを直接セット.

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdlib.h>

using namespace std;
typedef long long LL;
const int INF=2e9+1e8;
const int MOD=1e9+7;
const int MAX_SIZE=1005;

int first[MAX_SIZE*2],nnext[MAX_SIZE*2];
int edge[MAX_SIZE*2][3],dist[MAX_SIZE],cnt[MAX_SIZE],vis[MAX_SIZE];
int V,E;
bool spfa_bfs(int start)
{
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    memset(dist,0xf3,sizeof(dist));
    queue<int>q;
    q.push(start);
    vis[start]=1;
    dist[start]=0;
    while(!q.empty())
    {
        start=q.front();
        q.pop();
        vis[start]=0;
        int k=first[start];
        while(k!=-1)
        {
            int terminal=edge[k][1];
            if(dist[terminal]<dist[start]+edge[k][2])
            {
                dist[terminal]=dist[start]+edge[k][2];
                if(!vis[terminal])
                {
                    q.push(terminal);
                    cnt[terminal]++;
                    vis[terminal]=1;
                    if(cnt[terminal]>V) return false;
                }
            }
            k=nnext[k];
        }
    }
    return true;
}
int main()
{
    // printf("sb
");
    int ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        int i,j;
        scanf("%d %d",&V,&E);
        for(i=0; i<=1000; i++)
            first[i]=-1;
        for(i=0; i<E; i++)
        {
            int a,b,c,d,e,val1,val2;
            scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
            val1=d-c;
            val2=e-c;
            int xiaobiao=(i+1)*2-2;
            edge[xiaobiao][0]=a,edge[xiaobiao][1]=b,edge[xiaobiao][2]=val1;
            nnext[xiaobiao]=first[a];
            first[a]=xiaobiao;
            xiaobiao++;
            edge[xiaobiao][0]=b,edge[xiaobiao][1]=a,edge[xiaobiao][2]=val2;
            nnext[xiaobiao]=first[b];
            first[b]=xiaobiao;
        }
        int ans=spfa_bfs(0);
//        for(i=0;i<V;i++)
//            printf("%d ",dist[i]);
//        printf("
");

        if(!ans) printf("$$$
");
        else printf("%d
",dist[V-1]);
    }
    return 0;
}