問題設定
重み付き有向グラフを考える。エッジの重みは負になっても良いとする。
ここでは、そのグラフの中に重みの和が負になるループ(negative cycle)が含まれるかどうかを判定する方法を考える。
例えば、上のようなグラフを考える。上には "2->1->3->4->2", "2->3->4->2" という２つのループがある。
このループにそってエッジの重みを計算していくとそれぞれ3, 0となるので、negative cycleが存在しない。
もし、例えば"2->3"のエッジが重み2だとすると、後者のループはnegative cycleになる。
あるグラフが与えられた時に、そのグラフにnegative cycleがあるかどうかを判定したいとする。どのように判定すれば良いだろうか？
手法1 : Johnson’s algorithmを使って、すべてのcycleを列挙する
ナイーブに考えると、グラフ中のすべてのループを検出し、それの重みを計算していく方法が考えられる。
グラフ中のcycleをすべて列挙するアルゴリズムとして標準的なものにJohnson's algorithmというものがある。
アルゴリズムの詳細については触れないが、例えばnetworkxを使う場合simple_cyclesメソッドで取得できる。
>>> import networkx as nx
>>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
>>> G = nx.DiGraph(edges)
>>> list(nx.simple_cycles(G))
[[0, 2], [0, 1, 2], [0], [1, 2], [2]]
この手法の問題点は、一般にグラフの中に含まれるcycleの数がグラフのサイズに対して指数関数的に増えていくことである。少しでも大きなグラフになると、もう手に負えない。
実際にちょっと実験してみると、ノード数30、平均次数3のグラフでも非常に多くのループを含んでいることがわかる。
>>> G = nx.erdos_renyi_graph(10,0.1, directed=True)
>>> len(list(nx.simple_cycles(G)))
0
>>> G = nx.erdos_renyi_graph(20,0.1, directed=True)
>>> len(list(nx.simple_cycles(G)))
62
>>> G = nx.erdos_renyi_graph(30,0.1, directed=True)
>>> len(list(nx.simple_cycles(G)))
12869
手法2 : Floyd-Warshall algorithm
グラフに含まれるcycleの数は非常に多いのだが、求めたいのは負のcycleがあるかどうかだけである。全てのcycleを列挙する必要はない。
そういう時にFloyd-Warshall algorithmが使える。Floyd-Warshall algorithmはグラフに含まれるあらゆるノード対の間の最短距離を求めるアルゴリズム。
Dijkstra法はある特定のノード間距離を求める手法であるのに対して、Floyd-...は全ノードペア間の最短距離を求める手法である。
またDijkstraは負の重みがあるグラフに対しては使えないが、Floyd-...は負の重みがあっても利用できる。
アルゴリズムの説明はwikipediaに書いてあるので省略するが、隣接行列の積のようなものをひたすら計算していく。
（実際には各要素の$A_{ij}$の要素の計算の際に $\sum_k A_{ik}A_{kj}$ を計算するのではなく $\min_k(A_{ik}+A_{kj})$を計算する。）
networkxのコードから本質的な箇所のみ抜粋し、みやすいように整形すると以下のようになる。
def floyd_warshall(G, weight='weight'):
from collections import defaultdict
dist = defaultdict(lambda: defaultdict(lambda: float('inf')))
for u in G:
dist[u][u] = 0
for u, v, d in G.edges(data=True):
e_weight = d.get(weight, 1.0)
dist[u][v] = min(e_weight, dist[u][v]) # self loopが正の重みを持つ場合があるので、minを取る必要がある
for w in G:
for u in G:
for v in G:
if dist[u][v] > dist[u][w] + dist[w][v]:
dist[u][v] = dist[u][w] + dist[w][v]
return dist
dist[i][j]にノードi,jの（暫定の）最短距離が入っている。
一番外側のループ(wのループ）でその最短距離を更新していく。wの各イテレーションでは、wを通るパスによってu-v間の暫定最短距離が更新できるかどうかを判定し、wを経由することによって最短距離が更新できるのであれば、dist[i][j]を更新する。
計算コストはノード数の３乗に比例する。
このアルゴリズムでnegative cycleがあることを判定できる。distの対角要素が負になることを見れば良い。
distは単調に減るばかりなので、negative cycleの有無だけ確認したい場合は最内ループで判定すれば良い。
参照 : S. Hougardy, "The Floyd–Warshall algorithm on graphs with negative cycles"
def has_negative_cycle(G, weight='weight'):
from collections import defaultdict
dist = defaultdict(lambda: defaultdict(lambda: float('inf')))
for u in G:
dist[u][u] = 0
for u, v, d in G.edges(data=True):
e_weight = d.get(weight, 1.0)
dist[u][v] = min(e_weight, dist[u][v]) # self loopが正の重みを持つ場合があるので、minを取る必要がある
for w in G:
for u in G:
for v in G:
if dist[u][v] > dist[u][w] + dist[w][v]:
dist[u][v] = dist[u][w] + dist[w][v]
if u == v and dist[u][u] < 0:
return True
return False