ベルマンフォード法

単一始点最短経路（1つの頂点から他の頂点への最短経路）を解くアルゴリズム。

負の閉路（無限ループしてしまうやつ）を検知できる。

ベルマン「負」ォード法、なので負に対応している

実質DP

ベルマンフォード法は、DPみたいなものと考えると掴みやすい。

辺の更新は、頂点の数をN個とするとN-1回の更新でいい。

まず前提として「コストが負の辺は存在しない」というのがある。

なので、頂点Nからどこかを散歩して頂点Nに戻ってきたとき、散歩にかかる費用は必ず0以上になる。

費用がかかるんだったら、その散歩の部分削っていいよな、というおきもちになる。

よって、いちいち同じ頂点を2回訪れる必要はないことがわかる。

つまり全ての頂点を訪れるのは1回きりでよくて、結果更新回数はN回でいい。

上のやつは「頂点sからs以外の頂点への最短経路は必ず、最大でもN-1回以内の手数で見つけられる」みたいな解釈の仕方もできる。

そのように考えると、もしN回以上の手数の最短経路が新しく見つかったら「おかしい！！！」となって、「もしかして負閉路がある…？」みたいに気づくことができる。

そのような負閉路がある場所を「-INF」として更新を続けていくと、その場所から-INFがN-1ターン以内に全体に伝搬していく。（さっきの考え方の逆で）