Looking for algorithm Answers? Try Ask4KnowledgeBase
Looking for algorithm Keywords? Try Ask4Keywords

algorithmベルマンフォードアルゴリズム


備考

有向グラフGが与えられると、与えられたノードAからグラフ内の残りのノードまでの最短距離を求めることがしばしばあります。 Dijkstraアルゴリズムは最短経路を求める最も有名なアルゴリズムですが、与えられたグラフのエッジ重みが非負である場合にのみ機能します。しかし、 Bellman-Fordは、重みの一部が負であっても、与えられたノード(存在する場合)から最短経路を見つけることを目指しています。負のサイクルがグラフに存在する場合、最短距離が存在しないことがあります(この場合、サイクルを周回することで合計距離が無限に短くなります)。 ベルマンフォードはさらに、このようなサイクルの存在を判断することを可能にする。

アルゴリズムの総複雑さは、 O(V*E)であり、V - は辺の頂点数およびE数である

ベルマンフォードアルゴリズム 関連する例