ベルマン–フォード法

グラフ上の単一始点最短経路問題を解くためのアルゴリズム。ダイクストラ法とは異なり、辺の重みが負の場合でも正しく動作し、負の閉路の検出も可能である。全ての辺に対する緩和操作を頂点数分だけ繰り返すという構造上、ソーティング処理を必要としないが、計算量はO(nm)となり、一般的なグラフではダイクストラ法よりも低速である。新アルゴリズムはこの手法の「ソーティング不要」という特性を部分的に取り入れている。