ベルマン–フォード法
すると、始点から v までの経路は高々 i-1 個の辺からなる始点から v までの最短経路となる。帰納法上の前提により、i-1 回の反復後の v.distance は高々この経路の距離である。したがって、uv.weight + v.distance は高々 s から u への経路の距離である。i-番目の反復で、u.distance は uv.weight + v.distance と比較され、uv.weight + v.distance の方が小さければその値が設定される。したがって、i 回の反復後、u.distance は高々始点から uへの最短経路の距離であり、その経路には高々 i 個の辺がある。
負の重みの閉路がないなら、それぞれの最短経路には各頂点は高々1回出現する。したがって step 3 に至ったとき、それ以上の経路や距離の短縮は不可能である。逆に短縮できないとすると、頂点 v[0],..,v[k-1] の任意の閉路について、次が成り立つ。
v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight
閉路上で総和を求めると、v[i].distance の項と v[i-1 (mod k)].distance の項は相殺され、次の式が残る。
0 <= v[i-1 (mod k)]v[i].weight の 1 から k までの総和
すなわち、全ての閉路は負でない重みを持つ。