最短単一ソースパスアルゴリズム——SPFA

導入
Dijkstraは、分かりやすく、実用的で信頼性が高く、時間の複雑さがOI初心者に人気があることは間違いありませんが、辺権値が負の場合を処理できないという致命的な欠点があります.以下に、ブロガーの優先キュー最適化のDijkstraアルゴリズムを示します.　　

for(int i=1;iint nextnode,nextmin;
        int numnoww;
        while(true)
        {
            numnoww=minnow.size();
            if(numnoww==0)break;//     RE
            x=minnow.top();
            minnow.pop();
            if(!vis[x.dot])//         ，  continue
            {
                nextnode=x.dot;
                nextmin=x.len;
                break;
            }
        }
        if(numnoww==0)break;
        vis[nextnode]=true;
        for(int j=data[nextnode].size()-1;j>=0;j--)
        {
            int t=data[nextnode][j].dot;
            if(!vis[t]&&dist[t]>dist[nextnode]+data[nextnode][j].len)
            {
                dist[t]=dist[nextnode]+data[nextnode][j].len;
                //      
                x.dot=t;
                x.len=dist[t];
                minnow.push(x);//  
            }
        }
    }

この方法でノードにアクセスすると、ノードはアクセス済みとマークされるのは明らかです.一方、負の重み値エッジが存在する場合、別の負の重みエンドポイントにアクセスしたときにアクセスしたエンドポイントを最適化し続けることができますが、vis配列をtrueに変更したため更新できません.だから標準Dijkstraアルゴリズムで負の重み値を含む辺の問題をするのは純粋に運だ.このときSPFAアルゴリズムを用いてこの問題を解決することができる.SPFAアルゴリズムは1994年に西安交通大学段凡丁が提案したBellman Fordアルゴリズムのキュー最適化バージョンであり,その時間複雑度はO(ME)である.(多くのアルゴリズムが外国人が提案しているのを見て、中国人が作ったアルゴリズムは有木有を誇りに思っています(̀ω•́)っ ).
SPFAアルゴリズムの主な考え方
1.始点以外の点の距離(dist)をINFに初期化し、始点を0に初期化し、後続のステップが最適化されることを保証する.2.まず始点pushをキューに入れ、キューヘッダ要素は始点に接続されたすべての点のdist値を最適化する.以前のdist値よりも小さく、現在のキューにその点がない場合は、その点pushをキューに入れます.3.キューの先頭要素を繰り返し、キューに要素がないまで接続された点を最適化すると、すべての点から始点までの距離が最適化されます.
SPFAにおいて同じ点が複数回キューに参加できることは明らかであり,負の重みのあるエッジが存在する場合のdistの最適値を保証する.ブロガーは以下の問題を例題としています.http://ybt.ssoier.cn:8088/problem_show.php?pid=1379この操作を実現するには、次の変数が必要です.

queue <int> next;//    ，           ；         
int dist[2505];//           ；
bool now[2505];//               ；
struct sd
{
    int nextnode;//       
    int len;//        
};
sd x;//    push  
vector  data[2505];//      

メインプログラムコードを貼って、説明は注釈を参照してください.

//
int main()
{
    memset(now,false,sizeof(now));//       
    memset(dist,127,sizeof(dist));
    //        
    int city,road,start,endd,a,b,c,noww,p,v;
    scanf("%d%d%d%d",&city,&road,&start,&endd);
    for(int i=1;i<=road;i++) //        
    {
        scanf("%d%d%d",&a,&b,&c);
        x.nextnode=b;
        x.len=c;
        data[a].push_back(x);
        x.nextnode=a;
        data[b].push_back(x);
    }
    next.push(start);//   push   
    now[start]=true;
    dist[start]=0;//           0
    while(!next.empty())
    {
        noww=next.front();//  
        next.pop();
        now[noww]=false; //         false
        for(int i=data[noww].size()-1;i>=0;i--)
        {
            p=data[noww][i].nextnode;
            v=data[noww][i].len;
            if(dist[p]>dist[noww]+v)//   
            {
                dist[p]=dist[noww]+v;
                if(!now[p])//          
                {
                    now[p]=true;
                    next.push(p);
                }
            }
        }
    }
    printf("%d",dist[endd]);
    return 0;
}

注意:SPFAアルゴリズムでは、負の重みリングを持つ図の最短回路の問題を処理できないことは明らかです.(デッドサイクルは、いつまでも負の重みリングで検索されていた…)が、図中に負の重みリングが存在するか否かを判断できる.num配列カウントを1つ追加するだけで、メンバーがエンキューするたびに対応する値を1つ加算し、ある点のエンキュー回数が総点数マイナス1を超えると、必ずリングが存在し、異常情報が投げ出される.以上が今期ブログの全内私信ブロガーの交流と勉強を歓迎します.