SPFAアルゴリズムの概要

Bellman-Fordアルゴリズム
Dijkstraアルゴリズムは図の中で負の重みの辺があってはいけないことを要求して、もし負の重みの辺があるならば?負の重みエッジが存在する図についてBellman‐Fordアルゴリズムを用いて解いた.Bellman‐Fordアルゴリズムは反復思想に基づいている.図にn個の頂点、m個の辺があると仮定し、ソース点は1であり、基本的な手順は以下の通りである.

dis配列の初期化

dis[1]は0

に初期化された.

その他の初期化は+∞+infty+∞

m辺の弛緩操作を繰り返し,合計n−1回行った.

は、弛緩操作が行われるか否か(dis配列が変化するか否か)を判断し、弛緩が行われる場合は、負の重み回路が存在し、最短経路がないことを示す.そうでなければdis配列の値はソースポイントからの最短パスである.

ソース点Sが決定されると、dis[S]の距離が決定され、1回のエッジ緩和動作を経て、少なくとも1つの点の最短経路が決定される.反復緩和操作を繰り返し,n−1回のエッジ緩和操作を行った後,ソース点を除去したn−1個の頂点の最短経路を決定できる.n回目の緩和動作がまだ可能であれば,最短経路なしで負の重み回路が存在することを示す.
コード#コード#

for(int i=1;i<n;i++)//  n-1 
{
    for(int j=1;j<=m;j++)//m  
        dis[e[j].to]=min(dis[e[j].to],dis[e[j]].from+e[j].w);
}

SPFA
SPFAはキュー最適化のbellman-fordアルゴリズムであり,国内ではSPFAアルゴリズムと呼ばれている.bellman-fordアルゴリズムによるエッジ緩和操作では,前回の緩和で変化しなかった頂点からのエッジも緩和され,大量の冗長操作が存在する.SPFAアルゴリズムはこの状況を最適化し,変化する頂点からのエッジのみを緩和し,すべての頂点の距離が変化しなければアルゴリズムは終了する.基本操作:

初期化dis[1]は0、その他は+∞infty∞.

ソースポイント1入キュー

は、キューヘッダから頂点を取り出し、その点から出発するエッジを緩和し、最下位のdis推定値が変化し、キューに存在しない場合、その点をキューに追加する.

キューが空になるまでループを繰り返します.

コード#コード#

//SPFA
while(!q.empty())
{
	int t=q.front();q.pop();book[t]=0;
	for (int j=head[t];j!=-1;j=edge[j].next)
	{
		if (dis[edge[j].to]>dis[edge[j].from]+edge[j].w)
		{
			dis[edge[j].to]=dis[edge[j].from]+edge[j].w;
			if (!book[edge[j].to]) {q.push(edge[j].to);book[edge[j].to]=1;}
		}
	}
}

要素がキューにすでに存在する場合は、パスのみが更新され、再エンキューする必要はありません.1つのポイントは何度も出て、何度も入隊する可能性がありますが、同時にキューに何度も現れることはありません.
負の重み付けループの検出
SPFAでは,カウント配列を増やすことで,各点が緩和された回数を統計し,負の重みループが存在するか否かを判断することができる.

if (dis[edge[j].to]>dis[edge[j].from]+edge[j].w)
{
	dis[edge[j].to]=dis[edge[j].from]+edge[j].w;
	cnt[edge[j].to]++;
	if(cnt[edge[j].to]>=n)
	{
	    cout<<"   ";//       n ，      ，    w   。
	    return;
	}
	if (!book[edge[j].to]) {q.push(edge[j].to);book[edge[j].to]=1;}
}

出力パス

while(!q.empty())
{
	int t=q.front();q.pop();book[t]=0;
	for (int j=head[t];j!=-1;j=edge[j].next)
	{
		int v=edge[j].to, w=edge[j].w;
		if (dis[v]>dis[t]+w)
		{
			pre[v]=t; 
			dis[v]=dis[t]+w;
			if (!book[v]) {q.push(v);book[v]=1;}
		}
	}
}

pre配列を使用してノードの順方向ノードを記録し、パスを出力します.