ベルマン・フォード法は、グラフ理論において、ある始点から各頂点への最短経路を求めるためのアルゴリズムです。ダイクストラ法と同様に最短経路を求めるためのアルゴリズムであり、負の辺があっても対応できる点が特徴です。しかし、ダイクストラ法よりも計算量が多く、大規模なグラフには向きません。ベルマン・フォード法のアルゴリズムは以下の通りです。 始点sから各頂点までの距離をd[i]として、d[i]を無限大に初期化する。 始点sの距離d[s]を0とする。 辺を緩和する。各辺(u, v)について、以下の条件を満たす場合、d[v]を更新する。 d[v] > d[u] + w(u, v) 上記の辺緩和を全ての辺に…
ja.wikipedia.org