SPFAアルゴリズム

SPFA(Shotest Path Faster Algorithm)はBellman−Fordアルゴリズムの行列実現であり、不要な冗長計算を低減した.
アルゴリズムの大まかな流れは、キューを使ってメンテナンスされます.最初にソースをキューに追加します.列から元素を取り出して、彼と隣接するすべての点を緩和します.もしある隣の点がゆるみに成功すれば、それを入隊します.列が空になるまでアルゴリズムは終了します.
このアルゴリズムは、簡単に言えば、キュー最適化のBellman-fordを利用して、各点があまりにも多くの特徴を更新しないように発明されたこのアルゴリズムを利用しています.
SPFA――Shotest Path Faster Algorithmは、O(kE)の時間の複雑さの中でソースポイントを他のすべての点に求める最短ルートで、負の端を処理することができます.SPFAの実現はDijkstraやBellman_よりも大きいです.Fordはまだ簡単です
DistはSからI点までの現在の最短距離を表し、FaはSからIまでの現在の最短経路の中でI点より前の一点の番号を表している.スタート時はDistは全部「∞」で、Dist[S]=0のみで、Faはすべて0です.
行列を維持し、中には反復が必要な点が全部保存されています.初期時のキューの中には一点Sしかありません.各ポイントがキューにあるかどうかは、ブール配列で記録されます.
反復毎に、チームヘッドの点vを取り出し、順次にvから出発する辺v->uを列挙し、辺の長さをlenとし、Dist[v]＋lenがDist[u]より小さいかどうかを判断し、小さい場合はDist[u]を改善し、Fa[u]をvと表記し、Sからuまでの最短距離が小さくなるので、他の点を改善できる可能性がある.このように、列が空になるまで、つまりSからすべての最短距離が確定し、アルゴリズムを終了します.一つのポイントが入隊回数がnを超えると、負のリングがあります.
SPFAは形式的にも幅優先検索と非常に似ています.幅優先検索の中の一つのポイントが列から出たら再び列に入ることはできません.しかし、SPFAの一つのポイントは列を出た後に再び列に入れられるかもしれません.つまり、点が他の点を改善した後、時間が経ったら自分で改善されるかもしれません.このように繰り返します.他の点を反復点として改善するための点の平均回数をkとする点を設定し、通常の場合、kは2前後であることを証明する方法がある.
SPFAアルゴリズム(Shotest Path Faster Algorithm)は、単一ソースの最短経路問題を解決するためのアルゴリズムでもあり、与えられた重みは図Gとソースポイントsにあり、図Gの任意の点vについてsからvまでの最短経路を求める.SPFAアルゴリズムはBellman-Fordアルゴリズムの1つのキュー実装であり、不要な冗長計算を低減しました.彼の基本アルゴリズムはBellman-Fordと同じです.そして、次の方法で改善しました.1、2番目のステップは、すべてのノードを列挙するのではなく、列を通じて最適化された先駆的なキューを設立して最適化されるべき結点を保存します.最適化される度にチームの先頭結点uを取り出します.また、u点を離れることによって指し示す結点vは、u点の現在の最短経路推定値で緩和操作され、v点の最短経路推定値が調整され、v点が現在のキューにない場合、v点を列の最後に入れる.このようにして、列が空になるまで、列から結点を取り出して弛緩作業を行います.2、列が空かどうかを判断してサイクルを終了する以外に、負のループがあるかどうかを判断することができます.ある点が列に入る回数がV回を超えると負のループがあります.
SPFAアルゴリズムは、2つの最適化アルゴリズムSLFとLLL:SLF:Small Label Firstポリシーがあり、参加するノードがjであり、チームの最初の要素がiである場合、dist(j)＜dist(i)は、チームの先頭にjを挿入します.そうでなければ、チームの最後に挿入します.LLL:Large Label Lastポリシーは、チームの最初の要素iを設定し、キューのすべてのdist値の平均値はxであり、dist(i)＞xを行うと、iを列の最後に挿入し、dist(i)＜xを見つけるまで次の要素を検索し、iをペアに緩和操作を行う.SLFは速度を15~20%上げることができます.SLF＋LLLは約50%アップできます.実際の応用ではSPFAのアルゴリズム時間効率はあまり安定しておらず、最悪の場合の出現を避けるために、効率がより安定したDijkstraアルゴリズムが一般的に使用される.
C言語テンプレート

SPFA
void Spfa()
{
 for (int i=0; i<num_town; ++i)//   ，num_town       
    {
        dis[i] = MAX;
        visited[i] = 0;    
    }
int front=0,rear=1;//front    ，rear    
 dis[start] = 0;
    visited[start] = 1;
    Q[front]=start;//  ,Q    ，               
    while (front<rear){
        int temp = Q[front++];//  
        visited[temp]=0;
        for (int i=0; i<num_town; i++)
        {
            if (dis[temp] + road[temp][i] < dis[i])//      ，       COUNT  ，          V(   )  。
            {
                dis[i] = dis[temp] + road[temp][i];
                if (!visited[i])//       
                {
                    Q[rear++]=i;//  
                    visited[i] = 1;    
                }        
            }            
        }         
    }    
}