ダイクストラ法＋ヒープキュー＋経路表示（最短経路問題）

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

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

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

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

[グラフ]

ソースコード

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

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

heappush関数 の引数が３つになっています。（22行目、40行目）

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

[Google Colaboratory]

#---------- 入力例 ----------
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

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