ベルマン–フォード法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/20 14:47 UTC 版)
ベルマン–フォード法 (英: Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズム[1]の一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。名称は開発者であるリチャード・E・ベルマンと Lester Ford, Jr. にちなむ。
- ^ Dimitri P. Bertsekas (1992年3月). “A Simple and Fast Label Correcting Algorithm for Shortest Paths” (PDF). Networks, Vol. 23, pp. 703–709, 1993. 2008年10月1日閲覧。
- ^ Robert Sedgewick. Algorithms in Java. Third Edition. ISBN 0-201-36121-3. Section 21.7: Negative Edge Weights. http://safari.oreilly.com/0201361213/ch21lev1sec7
- ^ Jin Y. Yen. "An algorithm for Finding Shortest Routes from all Source Nodes to a Given Destination in General Network", Quart. Appl. Math., 27, 1970, 526–530.
[続きの解説]
「ベルマン–フォード法」の続きの解説一覧
- 1 ベルマン–フォード法とは
- 2 ベルマン–フォード法の概要
- 3 応用
- 4 参考文献
- ベルマン–フォード法のページへのリンク
