SPFA(Shortest path faster algorithm)で負閉路の検出

はじめに

単一始点最短経路問題を解く方法として、SPFA(Shortest path faster algorithm)というものがあります。

SPFAには、負閉路を含むグラフに適用すると無限ループに陥るという問題があります。そのため、重みが負の辺が存在するグラフを扱いたければ、何とかして負閉路の存在を検出してループを止める必要があります。

ただ、負閉路の検出をする方法をネットで検索しても、以下のページで紹介されている2種類の方法ぐらいしか見つかりませんでした(検索の仕方が悪いだけだと思いますが)。

頂点数を$N$としたとき、

1. 同じ頂点を処理した回数が$N$回以上なら負閉路あり
2. 各頂点に至る最短経路の辺の数が$N$個以上になったら負閉路あり

どちらも、頂点ごとに値を保持しなければなりません。

検出だけなら、もっとお手軽な方法があると思われるので、晒してみます。
(こちらの内容が間違っていてマサカリが飛んできたら記事ごと削除します)

基本となるコード

とりあえず、負閉路検出の無い素のコードを載せておきます。

import unittest
from collections import deque
INF=1_000_000_000_000_000_000

class UniqueQueue:
	def __init__(self,a=()):
		self.q=deque(a)
		self.s=set(self.q)
	def append(self,v):
		if v not in self.s:
			self.q.append(v)
			self.s.add(v)
	def popleft(self):
		v=self.q.popleft()
		self.s.remove(v)
		return v
	def __len__(self):
		return len(self.q)

def spfa(adj,x):
	n=len(adj)
	q=UniqueQueue([x])
	distance=[INF]*n
	distance[x]=0
	while q:
		s=q.popleft()
		for u,w in adj[s]:
			if distance[u]>distance[s]+w:
				distance[u]=distance[s]+w
				q.append(u)
	return distance

class Test(unittest.TestCase):
	def test(self):
		self.assertEqual(spfa([[]],0),[0])
		self.assertEqual(spfa([[(1,5),(2,3),(3,7)],[(0,5),(3,3),(4,2)],[(0,3),(3,1)],[(0,7),(1,3),(2,1),(4,2)],[(1,2),(3,2)]],0),[0,5,3,4,6])
		# self.assertIsNone(spfa([[(1,3),(2,5)],[(0,3),(2,2),(3,1)],[(0,5),(1,2),(3,-7)],[(1,1),(2,-7)]],0))

if __name__=='__main__':
	unittest.main()

入力は隣接リストと開始頂点、出力は各頂点までの距離のリストになります。
本体をシンプルに保つため、重複を許さないキューをクラス化して別途定義しています。
こちらに手を加えて、負閉路を含む場合にNoneを返すようにします。

方法1

stackoverflowで紹介されている方法その1です。
同じ頂点を処理した回数が$N$回以上なら負閉路ありと判定します。
開始頂点のvisitsをどうするか指定されておらず、適当に-1を入れているので(0のままだとまともに動作しない)、実装に誤りがある可能性があります。

def spfa1(adj,x):
	n=len(adj)
	q=UniqueQueue([x])
	distance=[INF]*n
	distance[x]=0
	visits=[0]*n
	visits[x]=-1
	while q:
		s=q.popleft()
		visits[s]+=1
		if visits[s]>=n:
			return None
		for u,w in adj[s]:
			if distance[u]>distance[s]+w:
				distance[u]=distance[s]+w
				q.append(u)
	return distance

方法2

stackoverflowで紹介されている方法その2です。
各頂点に至る最短経路の辺の数が$N$個以上になったら負閉路ありと判定します。

def spfa2(adj,x):
	n=len(adj)
	q=UniqueQueue([x])
	distance=[INF]*n
	distance[x]=0
	len_=[0]*n
	while q:
		s=q.popleft()
		for u,w in adj[s]:
			if distance[u]>distance[s]+w:
				len_[u]=len_[s]+1
				if len_[u]>=n:
					return None
				distance[u]=distance[s]+w
				q.append(u)
	return distance

方法3

SPFAのベースとなったベルマン–フォード法では、ループを$N-1$回繰り返した後に緩和できる箇所が残っていたら負閉路があると判断しています。

ループを$i$回繰り返した後、辺を$i$本以下たどった際の最短距離は最低限求まっている、という理屈です。

こちらをSPFAに適用すると、初回のループは開始頂点のみ、2回目のループは初回のループで緩和された頂点のみ、・・・という形で対応づけることができます。

ループの回数を検出するため、キューに特殊な記号-1を登録することにします。-1に行き着いたら、ループの回数を1回増やして、再度キューに-1を登録します。キューには常に-1が登録されている状態になるので、キューに-1以外の要素が登録されていない場合に「キューが空である」とみなすことにします。

def spfa3(adj,x):
	n=len(adj)
	q=UniqueQueue([x,-1])
	step=0
	distance=[INF]*n
	distance[x]=0
	while len(q)>1:
		s=q.popleft()
		if s<0:
			step+=1
			if step>=n:
				return None
			q.append(-1)
			continue
		for u,w in adj[s]:
			if distance[u]>distance[s]+w:
				distance[u]=distance[s]+w
				q.append(u)
	return distance

キュー内に-1しか存在しなくなってもstepが増え続けて最終的にn以上になるはずなので、ループではstepの判定だけ行って、ループを抜けてから負閉路の判定をするのもありです。(負閉路が無い場合に余計なループが発生しますが)

def spfa3a(adj,x):
	n=len(adj)
	q=UniqueQueue([x,-1])
	step=0
	distance=[INF]*n
	distance[x]=0
	while step<n:
		s=q.popleft()
		if s<0:
			step+=1
			q.append(-1)
			continue
		for u,w in adj[s]:
			if distance[u]>distance[s]+w:
				distance[u]=distance[s]+w
				q.append(u)
	return distance if len(q)<=1 else None

方法4

無限ループさえ回避できればよいので、負閉路が無い場合に、基本となるコードの外側のループが最大何回回る可能性があるかを求めて、それ以上ループが回ったら負閉路があると判定することにします。

「方法3」での各ループで最大何回外側のループが回るか考えると、初回は開始頂点のみで1回、それ以降は最悪全頂点を回る可能性があるので$N$回回ることなります(キューへの重複登録不可なので最悪でも$N$)。すべて合わせると、$N(N-1)+1$回が最大数であることが分かります。

def spfa4(adj,x):
	n=len(adj)
	q=UniqueQueue([x])
	distance=[INF]*n
	distance[x]=0
	for _ in range(n*(n-1)+1):
		s=q.popleft()
		for u,w in adj[s]:
			if distance[u]>distance[s]+w:
				distance[u]=distance[s]+w
				q.append(u)
		if not q:
			return distance
	return None

負閉路があるときに外側のループを$O(N^2)$回回す必要がありますが、最初のコードからの修正量は最低限となります。

まとめ

それぞれの方法を比較してみます。

方法	時間	メモリ	最適化
方法1	×	$O(N)$	〇
方法2	〇	$O(N)$	〇
方法3	△	$O(1)$	×
方法4	×	$O(1)$	×

時間 : 負閉路検出のために追加で必要な時間。最悪の時間は変わらないので○×で。
メモリ : 負閉路検出のために追加で必要なメモリ。
最適化 : 最初に載せたWikipedia内の最適化と併用可能か。

方法1

同じ頂点が$N$回処理されないと検出されないので、もっとも時間がかかります。メモリ消費も最多タイなので、この方法を採用する理由がありません。

方法2

最短経路の辺の数が$N$となった瞬間に検出できるので、もっとも速くなります。メモリ消費は多いですが、最適化との併用も可能です。

方法3

ループ回数より長い経路の最短路が含まれる可能性があるので、方法2より検出が遅くなります。キュー内の順番に依存するので、最適化との併用はできません。

方法4

時間はかかりますが、元ソースからの修正量は最小なので、とりあえず負閉路でも無限ループにならない保証がほしいだけであれば、採用してもいいかもしれません。