書記が数学やるだけ#632 ベルマンフォード法，ワーシャルフロイド法

ダイクストラ法では計算できない負の重みを持つ場合に，ベルマンフォード法やワーシャルフロイド法が使える。

問題

一つだけ重みを変えているが，これが計算で何をもたらすかに注目。

説明

ベルマン・フォード法は，辺を一通り巡回しながら最短経路を更新していく。ダイクストラ法よりは遅くなるものの，負の重みがある場合でも計算できる。なお，負閉路があると計算が収束しないため，最短経路は計算できないが，「辺の数-1」で計算が終わらないことを負閉路の存在として検出することはできる。

ワーシャル・フロイド法でも負の重みがある場合に最短経路を計算することができる。

解答

ベルマン・フォード法について実際に手順を追ってみる。始点を0，それ以外を∞として，一つ一つ辺を探索し距離が短くなるなら更新する。

例えば，この地点でA→Cが-2と更新される。

ここでDが更新される。

1巡目が終わった段階ではBがまだ更新されていない。

ここでBが更新される。

3巡目となると，更新される箇所はなくなる。

これ以上繰り返しても値は更新されない。よって以下がAからの最短距離であると計算できた。

次に一つだけ重みを変えた場合。

この段階で全ての値が更新されている。

ここでCが更新される。

ここでDが更新される。

これ以上繰り返すと，延々と値が下がり続ける。というのも，このグラフには負閉路が存在するためである。よってこちらのグラフについては最短距離を計算できない。

ということで(1)についてワーシャル・フロイド法を適用する。初期値は隣接行列である。

値の更新は，各3頂点に対して探索を行うことで実施される。例えば，B→Cは3だが，B→A→Cは2なので，BからCの最短距離が2に更新される。

最終的には以下の形となる。

本記事のもくじはこちら：