はじめに
こんにちは。Yuinaです。
今日は東京の駅間の最短経路を見つけて、表示するプログラムを作成しました。
解説していきます。よろしくお願いいたします!
作成したコード
import heapq
def dikstra(graph,start_node,end_node):
distances = {node: float('inf') for node in graph}
distances[start_node] = 0
pre_distances = {node: None for node in graph}
priority_queue = [(0,start_node)]
while priority_queue:
current_time,current_node = heapq.heappop(priority_queue)
if current_node == end_node:
break
if current_time > distances[current_node]:
continue
for neighbor,travel_time in graph.get(current_node,{}).items():
new_time = current_time + travel_time
if new_time < distances[neighbor]:
distances[neighbor] = new_time
pre_distances[neighbor] = current_node
heapq.heappush(priority_queue,(new_time,neighbor))
return distances[end_node] ,pre_distances
def root_path(pre_distances,end_node):
path = []
current = end_node
while current is not None:
path.append(current)
current = pre_distances.get(current)
return path[::-1]
TOKYO_MAP = {
'池袋': {'新宿': 5, '目白': 2, '高田馬場': 7, '巣鴨': 5, '板橋': 4},
'目白': {'高田馬場': 2},
'高田馬場': {'新大久保': 2, '練馬': 15},
'新大久保': {'新宿': 2},
'新宿': {'渋谷': 7, '池袋': 5, '品川': 15},
'渋谷': {'新宿': 7, '恵比寿': 2, '品川': 11},
'恵比寿': {'渋谷': 2, '品川': 9},
'巣鴨': {'池袋': 5, '上野': 10, '水道橋': 8},
'板橋': {'池袋': 4, '練馬': 10},
'練馬': {'板橋': 10, '高田馬場': 15},
'上野': {'巣鴨': 10, '浅草': 5, '東京': 3},
'浅草': {'上野': 5},
'品川': {'新宿': 15, '渋谷': 11, '恵比寿': 9, '東京': 7},
'水道橋': {'巣鴨': 8, '東京': 5},
'東京': {'上野': 3, '品川': 7, '水道橋': 5}
}
start = '新宿'
end = '東京'
min_time,pre_distances = dikstra(TOKYO_MAP,start,end)
shortest_path = root_path(pre_distances,end)
print(f"--- {start} から {end} までの最短経路（最速時間）---")
print(f"最短時間: {min_time} 分")
if min_time != float('inf'):
print(f"最短経路:{' ->'.join(shortest_path)}")
else:
print("駅間の経路は見つかりませんでした。")
解説
メソッドの解説をしていきます。
dikstraメソッド
こちらは、ダイクストラ法で最短ルートを見つけ出すメソッドです。
distances = {node: float('inf') for node in TOKYO_MAP}
distances[start] = 0
pre_distances = {node: None for node in TOKYO_MAP}
priority_queue = [(0, start)]
distancesにすべての場所への移動時間を初期化します。
distances = { ‘新宿’: float(‘inf’), ‘東京’: float(‘inf’), ‘渋谷’: float(‘inf’) }
という感じのイメージになります。
続いて、
distances[start] = 0で出発点を更新します。
distances = { ‘新宿’: 0, ‘東京’: float(‘inf’), ‘渋谷’: float(‘inf’) }
出発点を新宿にしたら、こんな感じでしょうかね。
pre_distances = {node: None for node in TOKYO_MAP}
は、これまでの経路を記録します。
こんなイメージです↓
| distances[i] | pre_distances | 意味 (矢印の向き) |
'新橋' | '品川' | 新橋へ最短で着くルートは、品川から来るものだ。 |
'品川' | '東京' | 品川へ最短で着くルートは、東京から来るものだ。 |
'東京' | None | 東京（出発地）の直前は存在しない。 |
続いて、
priority_queue = [(0,start_node)]
ですが、ダイクストラ法を始めるために最初のアイテムを準備し、キューに追加します。
表すと以下のようになります。
| 順序 | 要素 | 意味 |
| 1番目 | 0 | 移動時間（優先度の基準） |
| 2番目 | start_node | ノード名（駅名） |
続いて、最短ルートを探索します!!
while priority_queue:
current_time,current_node = heapq.heappop(priority_queue)
if current_node == end_node:
break
優先度キューに場所が残っている限り、調べ続けます。
移動時間が短い順から調べられるようにheapqを使います。
ここで、スキップ処理で遠回りなルートは無視します。
if current_time > distances[current_node]:
continue
続いて、今いる場所から行ける隣の場所をチェックします。
for neighbor,travel_time in TOKYO_MAP.get(current_node,{}).items():
new_time = current_time + travel_time
# current_time:出発地点から今いる場所までの合計最短時間
# traveL_time:駅(例:品川~新橋)の区間移動時間
# distances[neighbor]:これまで発見してきた最短経路
先ほど計算した、新しい合計時間(new_time)と隣の駅（neighbor）への最短時間を比較し、最短時間を更新します。
neighborの一つ手前の駅としてcurrent_nodeを記録します。
(新しい最短ルートは「今いる駅（current_node）を通ってきた」ものです)
そして、新しく見つかった、より短いルートを、ダイクストラ法の探索リストに組み込みます。
priority_queueは、最短時間を基準に自動で並び替えてくれる特別なヒープです。
(new_time,neighbor)は追加されるタプル(検索候補)です。
if new_time < distances[neighbor]:
distances[neighbor] = new_time
pre_distances[neighbor] = current_node
heapq.heappush(priority_queue,(new_time,neighbor))
return distances[end_node] ,predecessors
root_pathメソッド
ここでは、dikstraメソッドが見つけた情報を使って、
実際にどんなルートで移動したのか、内容を取得します。
path = [] #ここに経路を入れる
current = end_node # 現在地を目的地に設定
while current is not None:
path.append(current) # 経路を追加
current = pre_distances.get(current) # 1つ前の駅を取得
retun path[::-1] # リストを逆さまにして返す
目的地から出発地に向かって、pre_distancesの情報を頼りに
1つずつ場所を遡っていきます。
pre_distancesは現在地の1つ前のが格納されています。※再度掲載しておきます。
| キー (駅) | 値 (直前の駅) | 意味 (矢印の向き) |
'新橋' | '品川' | 新橋へ最短で着くルートは、品川から来るものだ。 |
'品川' | '東京' | 品川へ最短で着くルートは、東京から来るものだ。 |
'東京' | None | 東京（出発地）の直前は存在しない。 |
実行結果
ありがとうございました✨
