ベルマンフォード法による単一始点最短経路を求めるアルゴリズム | アルゴリズムロジック

ベルマンフォード法： 最短距離が更新されなくなるか、|V| 回目の更新が終わるまで以下を繰り返す全ての辺に対して、「d[v] = min{ d[u] + ( u から v への距離 ) }」という更新式を利用して最短距離を更新する|V-1| 回以内の更新で終了すれば負の閉路は存在しない。|V| 回まで更新が続けば負の閉路が存在する ※ 1. では、１回のループごとに１つの「最短距離が決まった頂点」を確定させていくイメージです。 ※ |V| 回までとするのは、負の閉路がある場合は最短距離は更新の度に小さくなってしまい、更新が止まらなくなるからです。 計算量 \(O(|V|\times |E|)\) 全ての辺を確認して更新を行うのに \(O(|E|)\) だけかかり、それを高々 |V-1| 回行う必要があります。 C++の実装例 struct Edge { long long from; lo