ベルマン・フォード法
読み方：べるまんふぉーどほう
【英】：Bellman-Ford algorithm
【英】：Bellman-Ford algorithm
1956年, フォードにより, また独立に1958年, ベルマンより示された最短路問題に対する基本的なアルゴリズムの1つ. 負の長さの枝が存在する場合にも適用可能で, 最短路が存在する場合には最短路を, 存在しない場合にはそのことを判定する. 局所的に点のラベルの書き換えを繰り返す. フォード・ベルマン法ともいう.
「OR事典」の他の用語
| グラフ･ネットワーク： | ネットワークフロー問題 フェンシェル型双対定理 プリム法 ベルマン・フォード法 ホールの定理 ポリマトロイド マッチング |
ベルマン–フォード法
(ベルマン・フォード法 から転送)
出典: フリー百科事典『ウィキペディア（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 参考文献
ベルマン-フォード法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/27 01:35 UTC 版)
「リチャード・E・ベルマン」の記事における「ベルマン-フォード法」の解説
ベルマン-フォード法は最短経路問題を解くアルゴリズムである。重み付けが常に正の場合はダイクストラ法の方が高速だが、負の重み付けも許容するような問題ではベルマン-フォード法を使う。
※この「ベルマン-フォード法」の解説は、「リチャード・E・ベルマン」の解説の一部です。
「ベルマン-フォード法」を含む「リチャード・E・ベルマン」の記事については、「リチャード・E・ベルマン」の概要を参照ください。
ウィキペディア小見出し辞書の「ベルマン・フォード法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- ベルマン・フォード法のページへのリンク
