ダイクストラ法+ヒープキュー+経路表示(最短経路問題)

ダイクストラ法+ヒープキュー+経路表示

前回記事では、ダイクストラ法ヒープキュー を使って最短経路問題の効率を上げて解きました。

今回は、さらに 最短経路 を表示します。

グラフは前回同様のものを使います。

[グラフ]

ソースコード

経路を表示するのはとても簡単です。

前回記事では ヒープキューコスト頂点名 を設定していましたが、さらに 経路 を設定するだけです。

heappush関数 の引数が3つになっています。(22行目、40行目)

(入力データの形式は前回記事と同様です)

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#---------- 入力例 ----------
nodes = { # ノード情報
'Start':{'edge':{'B':4, 'C':3}, # 隣の頂点までのコスト(頂点名:コスト)
'cost':0}, # 頂点Startまでの最小コスト
'B': {'edge':{'C':1, 'D':1, 'E':5}, # 隣の頂点までのコスト(頂点名:コスト)
'cost':float('inf')}, # 頂点Bまでの最小コスト
'C': {'edge':{'F':2}, # 隣の頂点までのコスト(頂点名:コスト)
'cost':float('inf')}, # 頂点Cまでの最小コスト
'D': {'edge':{'E':3}, # 隣の頂点までのコスト(頂点名:コスト)
'cost':float('inf')}, # 頂点Dまでの最小コスト
'E': {'edge':{'Goal':2}, # 隣の頂点までのコスト(頂点名:コスト)
'cost':float('inf')}, # 頂点Eまでの最小コスト
'F': {'edge':{'E':1, 'Goal':4}, # 隣の頂点までのコスト(頂点名:コスト)
'cost':float('inf')}, # 頂点Fまでの最小コスト
'Goal': {'edge':{}, # 隣の頂点までのコスト(頂点名:コスト)
'cost':float('inf')} # 頂点Goalまでの最小コスト
}
#----------------------------
import heapq

q = []
heapq.heappush(q, (0, 'Start', 'Start')) # スタート位置である頂点の(コスト,頂点名、経路)をヒープキューに追加

# ダイクストラ法(最もコストの小さい頂点を順番に確認していく方法)
while len(q): # キューがある限り実行
# 最もコストが小さい頂点名をヒープキューから取得
d = heapq.heappop(q) # コスト,頂点名,経路が返ってくる
min_node_name = d[1] # 頂点名
path = d[2] # 経路
if min_node_name == 'Goal': # ゴール位置の頂点だった場合
print('解:最小コストは', nodes['Goal']['cost']) # 最小コストを表示して終了
print('経路:', path)
break
# 最もコストが小さい頂点からの辺を繰り返しチェックする
for dst, cost in nodes[min_node_name]['edge'].items():
# 次の頂点までのコストが更新対象であれば更新
if nodes[dst]['cost'] > nodes[min_node_name]['cost'] + cost:
nodes[dst]['cost'] = nodes[min_node_name]['cost'] + cost
# コストを更新した頂点の(コスト,頂点名,経路)をヒープキューに追加
heapq.heappush(q, (nodes[dst]['cost'], dst, path + ' → ' + dst))

[実行結果]

解:最小コストは 8

経路: Start -> C -> F -> E -> Goal

最小コストの場合の、経路を表示 することができました。