図論アルゴリズム——SPFAアルゴリズム

SPFAアルゴリズムは単一ソース最短経路の最速アルゴリズムであり,時間複雑度はO(KE)Kが一般的に1または2であり,Eは辺数であり,たとえ彼がO(E)であってもよい.SPFAは多くの教科書に載っていませんが、主にSPFAは中国人が提案したもので、外国人はあまり知らないので、Dijkstraがアルゴリズムを取るほど人気がありません.人気はありませんが、アルゴリズム自体はいいです.SPFAはBellman-fordの最適化版で、単源最短経路で、負の重みリングSPFAがあるかどうかを調べることができます.主にBellman-fordの弛緩操作に余分な場所がたくさんあることを考慮して、キューで余分な場所を取り除きました.SPFAのアルゴリズムの過程は:0、先に説明して、dist[i]はsからiまでの最短経路を表して、map[i][j]はiからjまでのこの道の重み値を表して、sは起点を表して、cmp[i]はiが何回入隊したのです.1、初期化:dist配列を無限大にし、dist[s]を0にし、map[i][j]では、歩けばijという辺の重み値を置き、歩けないとINF(INFは無限大)にする.2、キューq,sを1つ設けて入隊する.3、キューの最初の要素を取り出して、この要素で他の要素を緩和します.つまり:

if(dist[v]+temp.secondfirst])
            {
                dist[temp.first] = dist[v]+temp.second;
                cmp[temp.first]++;q.push(temp.first);
                if(cmp[temp.first]>=n){std::cout<return 0;}
            }

ここではSTLのqueueとSTLのpair、queueを使っていますが、pairが知っている人は少ないと信じています.しばらくは2つの要素を貯蔵する容器として理解することができます.XXX.firstは最初の要素、XXXである.secondは2番目の要素です.STLのpairの詳細については、「pairヘルプ1」または「pairヘルプ2」にアクセスしてください.STLのqueueについてもっと知りたい場合は、「queueヘルプ1」または「queueヘルプ2」にアクセスしてください.キューが空の場合は、SPFAアルゴリズムが終了し、7 5にジャンプします.あるノードがn(ノード数)回以上キューに入ると,負の重みリングがあることを示し,「負の重みリングがある」と出力し,プログラムは終了する.6、3 7にジャンプし、出力し、プログラムを終了します.次は上のコードです.

#include
#include
#include
#include
#include
#include
#include
#include

int dist[1001],cmp[1001];
std::vector< std::list< std::pair <int,int> > > map1;
std::queue<int> q;
const int inf = 0x3f3f3f3f;

int main()
{
    int n,m,a,b,c,s;
    std::cin>>n>>m>>s;
    map1.resize(n+1);
    s--;
    for(int i = 0;istd::cin>>a>>b>>c;
        a--;b--;
        std::pair<int,int> temp (b,c);
        map1[a].push_back(temp);
    }
    memset(dist,0x3f,sizeof(dist));
    dist[s] = 0;
    q.push(s);cmp[s]++;
    while(1)
    {
        int v = q.front();q.pop();
        for(std::list< std::pair<int,int> >::iterator it = map1[v].begin();it!=map1[v].end();it++)
        {
            std::pair<int,int> temp = *it;
            if(dist[v]+temp.secondif(cmp[temp.first]>=n){std::cout<return 0;}
            }
        }
        if(q.empty()==true)break;
    }
    for(int i = 0;istd::cout<" ";
    return 0;
}