ベルマンｰフォード法

負のコストを許す

ただし、2つの頂点間を一方向に結ぶ有向辺のみ

逆方向は正のコストじゃないと、閉路になってしまい無限にコストを下げられることになり破綻する（最短経路が存在しなくなる）