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