以前このような記事を書きました。
こちらの記事で、車でお店を回る最短ルートを求めましたが、実は計算が中々終わらないケースを発見し、巡る店舗とコースを少し工夫しました。
その原因となった箇所がここ。
最短距離の計算、NetworkXのshortest_path()メソッドでした。
import networkx as nx
nx.shortest_path_length(graph, current_node, start_node, weight='length')
NetworkXの公式ドキュメントを見ると、method='dijkstra'がデフォルトになっていて、この方法にはルート探索のループに入ってしまうカラクリがあります。
改めて、パッケージの内容、理論はできるだけ良く理解しましょう！
代表的な計算方法
dijkstra法 と Bellman-Ford法 があります。
dijkstra法
ダイクストラ法と読みます。
起点からの複数の頂点のうち最小距離の頂点を確定させ、そこを起点として複数の頂点から最小距離を選ぶということを全ての頂点を多るまで繰り返します。簡単に言うと一歩ずつ最短の方向を探すということです。
Bellman-Ford法
ベルマンフォード法は、負のエッジを持つグラフ内の2点間の最短経路の検索、負のサイクルの検出、グラフ内の最大フローの計算など、さまざまな問題を解決できます。辺の緩和を全頂点に対して複数回繰り返します。
2つのアルゴリズムの長所短所
dijkstra法
- 効率的
- 負の閉路でループする
Bellman-Ford法
- 汎用的
- 計算に時間がかかる
| 特徴 | Dijkstra法 | Bellman-Ford法 |
|---|---|---|
| 負の重み対応 | 不可能 | 可能 |
| 負の閉路検出 | 不可能 | 可能 |
| 計算量 | O((V+E)logV) | O(V×E) |
| アルゴリズム | 貪欲法 | 全辺を順に緩和 |
| 実装の容易さ | やや複雑 | 簡単 |
| 使用場面 | 高速処理が必要な場合 | 負の重みや閉路がある場合 |
参考
アニメーションはWikipediaを参考にしました。