🐕
最短経路問題うんぬん
概要
最短経路問題に関して調べてまとめる。
経緯
最短経路問題に関して、概要は知っているが、ふと自分の中で整理したくなった。
前提
定義
最短経路問題
出発地から目的地までの最適な経路を求める問題。ダイクストラ法、ベルマンフォード法、ワーシャルフロイド法、ジョンソン法などがあり、様々な現実の問題に対して使用することができる。
ダイクストラ法
最短経路問題の中では一番有名な方法（知らんけど）
単一の始点の最短経路問題にて、閉路が全て正の場合に適用される。
- 始点に最短経路0を設定
- たどっていない点の中から、最も距離が短い頂点に移動して探索済みとする
- 探索済み設定の頂点から次に繋がる頂点までの移動距離を求め、その中で最小距離を持つ頂点に移動して探索済みとする
- 全ての頂点の最短距離が求められるまで2, 3を行う
ベルマンフォード法
最短経路問題の単一の始点の最短経路問題にて負の閉路がある場合に適用されるアルゴリズム。
フロー
- 始点に最短経路0、それ以外を無限大を設定
- 各頂点間の最短距離を調査、"基点となる頂点の最短距離+隣接する頂点するための重み < 隣接する頂点の最短距離"が成立したら隣接している頂点の最短距離を更新
- 負の閉路があるか確認し、存在するならその閉路には最短距離が存在しないため終了
- グラフの全ての頂点に対する最短距離が求まり、負の閉路が存在しなければ、これらの距離は最短経路の距離になる。
ワーシャルフロイド法
最短経路問題の中でも、全ての頂点間の最短経路を求めたい場合に適用されるアルゴリズム。
フロー
- 各頂点間の最短距離の推定値を初期化。各頂点自身への距離は0, それ以外の頂点間は無限大に設定
2. 各頂点に関して、全ての頂点のペアに対して距離を比較し、より短い方を新たな最短距離として更新
3. グラフの全ての頂点のペア間での最短距離が求まる。
例
触ってみないとなんともなので、ダイクストラ法で最短経路問題を実装してみる。
例で記載する分にはシンプルだが、ちょっと現実問題で使用してみたい感あり。
import heapq
def example_dijkstra(graph, start):
distances = {
node: float('infinity') for node in graph
}
# 始点に0を設定
distances[start] = 0
queue = [(0, start)]
# queueの数だけループ
while queue:
current_distance, current_weight = heapq.heappop(queue)
if distances[current_weight] < current_distance:
continue
for neighbor, weight in graph[current_weight].items():
distance = current_distance + weight
# 対象の頂点と隣接する頂点の最短距離を探す
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
example_graph = {
0: {1: 3, 2: 1},
1: {3: 1},
2: {1: 2, 3: 5},
3: {2: 3},
4: {}
}
print(example_dijkstra(example_graph, 0))
所感
一概に最短経路問題とは言ってもさまざまな方法で最短経路を解くことができるので、実装を繰り返して要件次第で使用する方法を変えれるようになることが重要だと感じた。
備考
雑賀木のところもあるので追記していく。
ラヴィットのスタジオでもある赤坂への電車の最短経路を求めるとか、追記してみる。
知らんけど。
参考文献
Discussion