ベルマンフォード法

最短経路を求めるアルゴリズムの一つ。すべての辺について距離の更新を繰り返す。ダイクストラ法より遅いが、重みが負の辺を含むグラフでも扱え、負の閉路があることも検出できる。

出発点から各頂点への最短経路を、すべての辺について距離の更新（緩和）を頂点数－1回繰り返して求めるアルゴリズム。負の重みの辺があっても正しく求められ、もう1回更新して距離が変わるなら、たどるほど距離が減り続ける負の閉路があると判定できる。計算量はO(VE)で、ダイクストラ法より遅い。

頂点（ノード）と、頂点どうしを結ぶ辺（エッジ）からなるグラフの性質を研究する数学の分野。向きのある有向グラフ、向きのない無向グラフ、辺に重みを持つ重み付きグラフがあり、最短経路や最小全域木、ネットワークの経路制御、SNSの関係の分析などに応用される。

重み付きグラフで、2つの頂点の間を結ぶ経路のうち、通る辺の重み（距離や費用）の合計が最小になる経路を求めること。負の重みが無ければダイクストラ法、負の重みがあればベルマンフォード法などを使い、カーナビの経路案内やネットワークの経路制御に応用される。

辺の重みが負でない重み付きグラフで、出発点から各頂点への最短経路を求めるアルゴリズム。最短距離が確定していない頂点のうち距離が最小のものを確定させ、そこから隣接する頂点の距離を更新することを繰り返す。OSPFの経路計算に使われている。