ベルマン・フォード法

【べるまんふぉーどほう (Bellman-Ford algorithm)】

1956年, フォードにより, また独立に1958年, ベルマンより示された最短路問題に対する基本的なアルゴリズムの1つ. 負の長さの枝が存在する場合にも適用可能で, 最短路が存在する場合には最短路を, 存在しない場合にはそのことを判定する. 局所的に点のラベルの書き換えを繰り返す. フォード・ベルマン法ともいう.