SPFAの紹介
なんかPKUのコードあさると時々見るSPFAというアルゴリズムを紹介します。
SPFAは単一始点の最短経路アルゴリズムで、負辺があっても動作します。
shortest path faster algorithmとかいうたいそうな名前がついてますが、普通はダイクストラに比べ遅いです。
オーダーはO(VE)なんですが、これだけ聞くとベルマンフォードで十分です。
SPFAはqueueを使ってベルマンフォードと大体同じことをします。
始点のコストを0にしてqueueに詰み、
queueが空でない間、そこからつながっている辺について、最短距離を更新できるか考えます。(ダイクストラ法のように)
また、ある頂点vがqueueに入っているかの配列を持っておき、すでにqueueに入っているなら最短距離を更新するだけです。
最短距離を更新できて、queueにないならqueueに入れます。
ちょっと想像すると、割と平面的なグラフでははやそうです。少なくともベルマンフォードより遅くなったことはありません
負閉路検出にも使えるらしい(実際にAC取ったこともあります)が、何故うまくいくかよく分からないので、ここでは解説しません・・・
//s:=始点 dst[i]:=iへの最短距離 inQ[i]:=iがqueueにあるか for(int i=0;i<n;++i) dst[i]=INF,inQ[i]=0; queue<int>q; inQ[s]=1;q.push(s);dst[s]=0; while(!q.empty()){ int cur=q.front();q.pop(); inQ[cur]=0; for(int i=head[cur];i!=-1;i=nxt[i]){//リストを走査 pair<int,int>& e=es[i];//(行き先,辺のコスト) if(dst[e.first]>dst[cur]+e.second){ dst[e.first]=dst[cur]+e.second; if(!inQ[e.first]){ inQ[e.first]=1; q.push(e.first); } } } }
1回、dijkstraでやけに時間制限が厳しいときSPFA書いたら通ったことがあります。ケースによりますが、爆速なこともあるらしい