ベルマン–フォード法
負の辺重みを持つグラフでも使える最短経路アルゴリズム。ダイクストラ法の前提が成り立たない場面での頼れる従兄弟。
全ての辺の緩和をV-1回繰り返し、もう一回繰り返すことで負閉路を検出する。計算量はO(V·E)で、ダイクストラ法のO((V+E) log V)より遅いが、負の重みを扱える。
古いが今も現役のRIP（Routing Information Protocol）、金融グラフの裁定取引検出などを支えている。競合としては全点対最短経路のフロイド–ワーシャル法や、疎グラフ向けのジョンソン法がある。