ベルマンフォード法
グラフ理論における単一始点最短経路問題を解決するアルゴリズムの一つ
重み付きグラフにおいて、ある始点から他の全ての頂点への最短経路を求める ことができる
グラフ内の各頂点について、始点からその頂点までの最短経路の長さを更新していく
この更新は、グラフの辺の数を上限として繰り返し行われ 、最終的に全ての頂点への最短経路が求められる
ベルマンフォード法
単一始点最短経路問題：ある始点から他の全ての頂点への最短経路を求める問題
負の閉路検出：グラフ内に負の閉路が存在するかどうかを判定する問題
通貨間の換算：為替レートをグラフの辺の重みとみなし、通貨間の最適な換算経路を求める問題
ベルマンフォード法とは？ 10分でわかりやすく解説｜ネットアテスト
関連：ダイクストラ法、最短経路問題