ベルマン–フォード法 - Wikipedia

ベルマン–フォード法 (英: Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズム[1]の一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。名称は開発者であるリチャード・E・ベルマンと Lester Ford, Jr. にちなむ。 グラフに「負閉路」(negative cycle) が含まれるとき、すなわち辺の重みの総和が負になるような閉路が存在するとき、好きなだけ小さな重みを持つ歩道を取れるので、「最短」経路は定まらない。このためベルマン-フォード法も負閉路が始点から到達可能である場合は正しい答を出せないが、負閉路を検出してその存在を報告することはできる。 ロバート・セジウィックによ

[KatagiriSo]

負の重みもある場合。

[ma__ko__to]

“Bellman-Ford algorithm”

[tanakaBox]

重みつき有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種

[shiumachi]

"重みつき有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種であり、各辺の重みは負数であってもよい"