ベルマン–フォード法
ベルマン–フォード法の基本構造はダイクストラ法とよく似ているが、ダイクストラ法が総当り的に未処理の重みが最小のノードを選択して緩めるのに対して、ベルマン–フォード法は頂点数を |V|としたとき、全辺を緩めることを単に|V| − 1 回繰り返す(初期状態で始点以外の頂点の始点からの距離は無限大にしておき、処理の途中段階で各頂点の始点からの最短距離と思われる距離に置き換えていく。これを relaxing(=「緩める」「緩和」など)と称する)。負の閉路がなければ最短経路上の各頂点は高々1回しか出現しないので、反復によって最短距離が正確にグラフ全体に伝播する。重みが正であることを前提とした構造上の仮定に基づく貪欲法的手法とは異なり、この直接的な方法はより汎用的である。
ベルマン–フォード法の実行時間は O(|V|·|E|) で、|V|と|E|はそれぞれ頂点数と辺数である。