hogloidのブログ

へなちょこ

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書いたら通ったことがあります。ケースによりますが、爆速なこともあるらしい