SPFA最短

単一ソースの最も短絡的なSPFAアルゴリズムのフルネームを求めて:Shotest Path Faster Algorithmです.     SPFAアルゴリズムは西南交通大学段凡丁が1994年に発表したものです.    名前から分かるように、このアルゴリズムは効率的に優れている.     多くの場合、所与の図には負権辺があります.この時Dijkstraなどのアルゴリズムは使う場所がなくなりました.Bellman-Fordアルゴリズムの複雑さが高すぎて、SPFAアルゴリズムが役に立ちました.spfaアルゴリズムは最も短絡的な万能アルゴリズムと呼ばれる.    簡潔のために、重み付け図Gに負の回路が存在しないこと、すなわち最短経路が必ず存在することを約束します.もちろん、アルゴリズムを実行する前に、負の権利ループがあるかどうかを判断するために、トポロジ順序付けを行うことができる.    配列disで各接合点の最短経路推定値を記録し、隣接行列または隣接テーブルで図Gを保存することができます.隣接テーブルの使用を推奨します.
spfaのアルゴリズム思想(動的近似法):    先進的な先駆的なキューqを設定して最適化すべき結点を保存し、最適化する度に、チームの先頭結点uを取り出し、u点を離れる現在の最短経路推定値で、u点から指す結点vを緩和操作し、v点の最短経路推定値が調整され、v点が現在のキューにない場合は、v点を列の最後に入れる.このようにして、列が空になるまで、列から結点を取り出して弛緩作業を行います.     緩和操作の原理は有名な定理です.「三角形の両側の和は第三辺より大きい」という情報学では三角不等式と呼ばれています.結点i,jを緩和するということは、dis[j]>dis[i]＋w[i,j]かどうかを判定し、この式が成立するとdis[j]をdis[i]＋w[i,j]に縮小し、そうでなければ動かない.     SFFAアルゴリズムはどのように行われるかを以下の例で説明する.
広捜bfsとの違い:    SPFAは形式的にも広さ(幅)優先検索と非常に似ています.違いはbfsの中の一つのポイントが列から出たら、再び列に入ることはできません.しかし、SPFAの一つのポイントは列を出た後に再び列に入れられるかもしれません.つまり、点が他の点を改善した後、時間が経ったら自分で改善されるかもしれません.このように繰り返します.
負のループの有無を判断する:
あるポイントが列に入る回数がN回を超えると負のリングがあります(SPFAは負のループを持つ図を処理できません)
 アルゴリズムの説明:

 1 void  spfa(s);  //    s           
 2     for i=1 to n do { dis[i]=∞; vis[i]=false; }   //      s   ，    
 3     dis[s]=0;  // dis[  ]  0
 4     vis[s]=true; //  s   
 5     head=0; tail=1; q[tail]=s; //  s  ,        
 6     while headdo {
 7        head+1;  //    
 8        v=q[head];  //    v
 9        vis[v]=false;  //   v   ，      
10        for    (v,i)  //     v       
11         if (dis[i]>dis[v]+a[v][i])  //          
12          dis[i] = dis[v] + a[v][i]   //  dis[i]
13         if (vis[i]=false) {tail+1; q[tail]=i; vis[i]=true;} //    ，     
14     } 

      ：

/*********************************************/  
//  d          dis  ，     i         
//  c         i       
//  vis            ， dijkstra  s      
//            ，w       
/*********************************************/  
bool spfa_bfs(int s) // s       
{  
    queue  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;  

最短経路自体はどう出力しますか?
    一つの図では、結点Aから結点Eまでの最短経路長だけを知っています.時々意味が大きくないことがあります.この図は地図のモデルであれば、最短の経路長を算出した後、私達はいつも「どうやって行けばいいですか?」と説明してから問題を解決します.どのように計算過程で最短経路を記録して、最後に出力しますか?
    私たちはpath[]配列を定義し、path[i]は源点sからiまでの最短距離の中で、結点iの前の結点の番号(親の結点)を表し、結点uによって結点vを緩和しながら、Path[v]=uをマークし、記録の作業が完了しました.
    どうやって出力しますか?私達が記録しているのは各点の前の点は何ですか?出力は一番前から後ろに出力します.これは簡単です.再帰すればいいです. 

 1 c++ code:
 2 void printpath(int k){
 3     if (path[k]!=0) printpath(path[k]);
 4     cout << k << ' ';
 5 }
 6 
 7 pascal code:
 8 procedure printpath(k:longint);
 9   begin
10     if path[k]<>0 then printpath(path[k]);
11     write(k,' ');
12   end;
13 
14 spfa    (    )：
15 c++ code:
16 void spfa(int s){
17     for(int i=0; i<=n; i++) dis[i]=99999999; //     i s   
18     dis[s]=0; vis[s]=1; q[1]=s;       ,s   
19     int i, v, head=0, tail=1;
20     while (head<tail){       
21         head++; 
22         v=q[head];       
23         vis[v]=0;         ，                 ，    
24         for(i=0; i<=n; i++)       
25            if (a[v][i]>0 && dis[i]>dis[v]+a[v][i]){  
26                 dis[i] = dis[v]+a[v][i];        
27                 if (vis[i]==0){        i     ，  
28                     tail++;
29                     q[tail]=i;
30                     vis[i]=1;
31                 }
32            }
33         
34     }
35 }
36 
37 pascal code:
38 procedure spfa(s:longint);
39   var i,j,v,head,tail:longint;
40   begin
41     for i:=0 to n do dis[i]:=99999999;
42     dis[s]:=0; vis[s]:=true; q[1]:=s;
43     head:=0;tail:= 1;
44     while headdo
45        begin
46          inc(head);
47          v:=q[head];
48          vis[v]:=false;
49          for i:=0 to n do
50            if dis[i]>dis[v]+a[v,i] then
51              begin
52                dis[i]:= dis[v]+a[v,i];
53                if not vis[i] then
54                  begin
55                    inc(tail);
56                    q[tail]:=i;
57                    vis[i]:=true;
58                  end;
59              end;
60 
61       end;
62   end; 

spfa最適化——深さ優先検索dfs
         上記のspfa標準アルゴリズムでは、結点uを更新(緩和)するたびに、この結点が列の中にない場合は、直接に入隊します.
    しかし,負のループがある場合,上記アルゴリズムの時間複雑性はO(nm)に縮退した.改善できますか?
    深度検索を使ってみます.コア思想は毎回結点uを更新する時に、その結点から再帰的に次の反復を行います.

  dfs  spfa  ：

 1 pascal code：
 2 procedure spfa(s:longint);
 3   var i:longint;
 4   begin
 5     for i:=1 to b[s,0] do  //b[s,0]    s       
 6            if dis[b[s,i]]>dis[s]+a[s,b[s,i]] then  //b[s,i]  s    i        
 7              begin
 8                dis[b[s,i]]:=dis[s]+a[s,b[s,i]];
 9                spfa(b[s,i]);
10              end;
11   end; 
12 
13 C++ code：
14 void spfa(int s){
15     for(int i=1; i<=b[s][0]; i++)  //b[s,0]    s       
16        if (dis[b[s][i]>dis[s]+a[s][b[s][i]]){  //b[s,i]  s    i        
17         dis[b[s][i]=dis[s]+a[s][b[s][i]];
18         spfa(b[s][i]);
19        }
20 }

         キューに比べて、深さ優先検索は先天的な利点があります.ループを一周して、遍歴した結点に戻ると負のループがあります.ほとんどの場合の時間複雑度はO(m)レベルです.
    深度検索を使ってみます.コア思想は毎回結点uを更新する時に、その結点から再帰的に次の反復を行います.
    World Rings(ACM-ICPC Centrual European 2005)については、676点、100000辺、負のループdfsを検索するには219 msしかかかりません.
    簡単なデータ構造とアルゴリズムはある程度大きな問題を解決した.
負のループがあると判断した条件は、現在の検索スタックの中のいずれかの結点を改めて通過します.
 
spfa最適化——前星最適化
         星形表示法の思想は隣接表表示法の思想とある程度似ています.各結点については、この結点から出発するすべての弧も記録されているが、一方向チェーン表ではなく単一の配列表現を採用している.つまり、この配列にはまず、結点1から出発するすべての弧が格納され、次にノード2から出発するすべての孤立が格納され、これに類推して、最後に結点nから出発するすべての孤立が格納される.各弧については、その起点、終点、権力の数値などの情報を順次保存します.これは実際には、すべての弧に対して順序と番号を与えることに相当し、同じ点から出発する弧の順序は任意に並べることができる.また、各ノードから出発するすべての弧を迅速に検索できるようにするために、私たちは通常、各ノードから出発する弧の開始アドレス(すなわち、弧の番号)を1つの配列で記録する.この表示法では、各結点から出発するすべての弧を素早く検索することができます.この星形表現法は、前方星形(forward star)表示法といいます.
    例えば、下図のように、アーク(1,2)、(l,3)、(2,4)、(3,2)、(4,3)、(4,5)、(5,3)、および(5,4)はそれぞれ8,9,6,4,0,7,6,3とする.この場合、ネットワーク図は、順星形で次のように表されます.
  

      ：

 1 #include 
 2 using namespace std;
 3 int first[10005];
 4 struct edge{
 5     int point,next,len;
 6 } e[10005];
 7 void add(int i, int u, int v, int w){
 8         e[i].point = v;
 9         e[i].next = first[u];
10         e[i].len = w;
11         first[u] = i;
12 }
13 int n,m;
14 int main(){
15     int u,v,w;
16     cin >> n >> m;
17     for (int i = 1; i <= m; i++){
18         cin >> u >> v >> w;
19         add(i,u,v,w);
20     }  //        
21     for (int i = 0; i <= n; i++){
22         cout << "from " << i << endl;
23         for (int j = first[i]; j; j = e[j].next)  //       
24             cout << "to " << e[j].point << " length= " << e[j].len << endl;
25     }
26 }

資料から:
http://blog.csdn.net/WR_technology/articale/detail/51254054
http://blog.csdn.net/xunalove/article/details/70045815
転載先:https://www.cnblogs.com/curo0119/p/8515811.html