目的
ある頂点から他の頂点への最短距離を求める。(単一始点最短経路)負のコストを持つ辺があっても利用可能。
原理
グラフの頂点数を$V$,辺の数を$E$とする。各頂点への最小コストを記録するリスト$d$を作成する。ここで、自身の点への距離は0で確定、他の点への距離はINFとする。
ここから、辺をすべて見て最短距離を更新していく。具体的に、辺$e$が頂点$from$から頂点$to$に向けてコスト$cost$という情報を持つとすると、
$$d[from] + cost < d[to]$$
となるとき、$d[to]$の値が$d[from] + cost$に更新される。
すべての辺を見るという操作を合計$V - 1$回行えば、負閉路がない場合にはすべての最小コストが確定する。つまり、$V$回目においてまだ最小コストの更新が行われた場合には負閉路を持つということで、正しい最小コストは求められない。
では、なぜ$V - 1$回のループで操作を完了させていいのか。自分の理解の仕方を説明する。ある頂点への最小コストとなる経路の中に、同じ頂点は2度と含まれない。含まれるとしたら負閉路があるということでそもそも正しい経路は求まらない。以上より、ある頂点への最短経路に含まれる辺の数は最大でも$V - 1$本である。この後のコードを確認すれば分かるのだが、辺の並びは入力順である。(幅優先探索のように近い順に調べるわけではない)つまり、$V - 1$本の最短経路を求める過程を考える。うまくいけば1回のループで前から順に辺が辿られ、この最短経路が求まるかもしれない。しかし、調べる辺の順がきれいに後ろから並んでしまっているとする。この時、前の辺が調べられていないとそれより後ろの辺を最短経路の一部とは考えられない。($from$までの距離がINFもしくは最小コストではないため)つまり、このケースでは1回のループにつきこの最短経路のうち前から1つずつしか求まらない。よって、これが最悪のケースで、$V - 1$回のループを必要とする。
※なら、幅優先探索的に近い順に調べればと思い実装しましたが、負閉路があると無限に値が更新され続けてしまうのでそこの工夫が必要な気がしました。正のコストのみのときについては会津オンラインのダイクストラの問題に投げたところ正解となったのでなんかこれにも名前付いているのかなあ。
計算量解析
最悪、すべての辺を見る操作を$V - 1$回行うので計算量は$O(EV)$。
実装
# O(EV)
def bellman_ford(s):
d = [float('inf')]*n # 各頂点への最小コスト
d[s] = 0 # 自身への距離は0
for i in range(n):
update = False # 更新が行われたか
for x, y, z in g:
if d[y] > d[x] + z:
d[y] = d[x] + z
update = True
if not update:
break
# 負閉路が存在
if i == n - 1:
return -1
return d
n, w = [int(x) for x in input().split()] # n:頂点数, w:辺の数
g = []
for _ in range(w):
x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
g.append([x, y, z])
g.append([y, x, z]) # 有向グラフでは削除
print(bellman_ford(0))
おわりに
コードについてもですが今回は考え方が結構不安なのでもしよければアドバイスください!