Pythonで学ぶアルゴリズム 第25弾：ダイクストラ法

#Pythonで学ぶアルゴリズム< ダイクストラ法 >

はじめに

基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第25弾としてダイクストラ法を扱う．

ダイクストラ法

ベルマン・フォード法のときと同じ経路を考える．以下の経路である．

丸で囲まれたところは目的地であり，それらを結ぶ矢印が道とする．矢印の近くにある数値はその道（矢印）を通る時の距離（コスト）である．また矢印には始点と終点があり，逆走はしないものとする．この経路に対して，ダイクストラ法を適用していく．

ダイクストラ法はベルマン・フォード法と似ているが，ベルマン・フォード法がすべての辺に対して処理を繰り返すのに対し，ダイクストラ法では選択する頂点を工夫することで効率よく最短経路を探すことができる．コストの更新の条件および更新方法はベルマン・フォード法と同じ．ダイクストラ法はベルマン・フォード法よりも効率がよく高速に解けるが，辺の値が負の場合には使えないことに注意する．今回の経路では存在しない．






次に示す図は最終結果である．

ここまでで，最短経路が得られた．図の緑で表す矢印がその経路を示している．今回はA→C→F→E→Gと進むのが最短経路(最小コスト)であるということが分かる．ここで，上図のそれぞれにおける表に注目すると，途中でばつがつけられそれ以上の探索を止めている箇所がいくつか見られる．これは，ある地点までのコスト，つまりある列に2つ以上の丸が付けられたとき最小のものだけを扱うということを意味する．ゆえに，ばつのつけられている列には2つ以上の丸があることが分かる．
「ばつがつけられるか，ゴールまで行くか」を満たすまで探索は続く．なお，表において，黄色で塗りつぶした箇所はその列における最小コストを示している．少なくとも最短経路はすべて黄色で塗りつぶされた箇所を通っていることが分かる．ただし，すべての列の最小コストを通るわけではない．

実装

先ほどの説明をもとにPythonでの実装をする．今回は3つのパターンで実装している．

実装１：ダイクストラ法

単に，ダイクストラ法を行うプログラム．そのソースコードとそのときの出力を以下に示す．

ソースコード

dijkstra1.py

"""
2021/01/29
@Yuya Shimizu

ダイクストラ法
"""

def dijkstra(edges, num_node):
    """ 経路の表現
            [終点, 辺の値]
            A, B, C, D, ... → 0, 1, 2, ...とする """
    node = [float('inf')] * num_node    #スタート地点以外の値は∞で初期化
    node[0] = 0     #スタートは0で初期化

    node_name = [i for i in range(num_node)]     #ノードの名前を0~ノードの数で表す

    while len(node_name) > 0:
        r = node_name[0]

        #最もコストが小さい頂点を探す
        for i in node_name:
            if  node[i] < node[r]:
                r = i   #コストが小さい頂点が見つかると更新

        #最もコストが小さい頂点を取り出す
        min_point = node_name.pop(node_name.index(r))

        #経路の要素を各変数に格納することで，視覚的に見やすくする
        for factor in edges[min_point]:
            goal = factor[0]   #終点
            cost  = factor[1]   #コスト

            #更新条件
            if node[min_point] + cost < node[goal]:
                node[goal] = node[min_point] + cost     #更新

    return node

if __name__ == '__main__':
    Edges = [
        [[1, 4], [2, 3]],             # ← 頂点Aからの辺のリスト
        [[2, 1], [3, 1], [4, 5]],   # ← 頂点Bからの辺のリスト
        [[5, 2]],                       # ← 頂点Cからの辺のリスト
        [[4, 3]],                       # ← 頂点Dからの辺のリスト
        [[6, 2]],                       # ← 頂点Eからの辺のリスト
        [[4, 1], [6, 4]],             # ← 頂点Fからの辺のリスト
        []                                # ← 頂点Gからの辺のリスト
        ]
    
    #今の目的地の数は7つ（0~6: A~G）
    node_num = 7

    opt_node = dijkstra(Edges, node_num)

    #以下は結果を整理するためのコード
    node_name = []
    for i in range(node_num):
        node_name.append(chr(ord('A') + i))    
    result = []
    for i in range(len(opt_node)):
        result.append(f"{node_name[i]} : {opt_node[i]}")
    print(f"'目的地:そこまでの最小コスト'\n\n{result}")

出力

'目的地:そこまでの最小コスト'

['A : 0', 'B : 4', 'C : 3', 'D : 5', 'E : 6', 'F : 5', 'G : 8']

実装２：ダイクストラ法: ヒープによる優先度付きキューを用いて

ヒープによる優先度付きキューを用いることで，計算量を小さくできるらしい．
ヒープソートのときに使ったheapqモジュールを使って，ヒープによる優先度付きキューを用いたダイクストラ法を行うプログラム．そのソースコードとそのときの出力を以下に示す．

ソースコード

dijkstra2.py

"""
2021/01/29
@Yuya Shimizu

ダイクストラ法（ヒープによる優先度付きキューを用いて）
"""
import heapq

def dijkstra(edges, num_node):
    """ 経路の表現
            [終点, 辺の値]
            A, B, C, D, ... → 0, 1, 2, ...とする """
    node = [float('inf')] * num_node    #スタート地点以外の値は∞で初期化
    node[0] = 0     #スタートは0で初期化

    node_name = []
    heapq.heappush(node_name, [0, 0])

    while len(node_name) > 0:
        #ヒープから取り出し
        _, min_point = heapq.heappop(node_name)
        
        #経路の要素を各変数に格納することで，視覚的に見やすくする
        for factor in edges[min_point]:
            goal = factor[0]   #終点
            cost  = factor[1]   #コスト

            #更新条件
            if node[min_point] + cost < node[goal]:
                node[goal] = node[min_point] + cost     #更新
                #ヒープに登録
                heapq.heappush(node_name, [node[min_point] + cost, goal])

    return node

if __name__ == '__main__':
    Edges = [
        [[1, 4], [2, 3]],             # ← 頂点Aからの辺のリスト
        [[2, 1], [3, 1], [4, 5]],   # ← 頂点Bからの辺のリスト
        [[5, 2]],                       # ← 頂点Cからの辺のリスト
        [[4, 3]],                       # ← 頂点Dからの辺のリスト
        [[6, 2]],                       # ← 頂点Eからの辺のリスト
        [[4, 1], [6, 4]],             # ← 頂点Fからの辺のリスト
        []                                # ← 頂点Gからの辺のリスト
        ]
    
    #今の目的地の数は7つ（0~6: A~G）
    node_num = 7

    opt_node = dijkstra(Edges, node_num)

    #以下は結果を整理するためのコード
    node_name = []
    for i in range(node_num):
        node_name.append(chr(ord('A') + i))    
    result = []
    for i in range(len(opt_node)):
        result.append(f"{node_name[i]} : {opt_node[i]}")
    print(f"'目的地:そこまでの最小コスト'\n\n{result}")

出力

'目的地:そこまでの最小コスト'

['A : 0', 'B : 4', 'C : 3', 'D : 5', 'E : 6', 'F : 5', 'G : 8']

実装３：ダイクストラ法: 経路を記録する

今までのものは，ある地点での最小コストしか示しておらず，実際の経路は出力できていない．したがって，次はダイクストラ法において，経路を記録するプログラムである．そのソースコードとそのときの出力を以下に示す．

ソースコード

dijkstra3.py

"""
2021/01/29
@Yuya Shimizu

ダイクストラ法（ヒープによる優先度付きキューを用いて）
経路を記録する
"""
import heapq

def dijkstra(edges, num_node, Goal):
    """ 経路の表現
            [終点, 辺の値]
            A, B, C, D, ... → 0, 1, 2, ...とする """
    node = [float('inf')] * num_node    #スタート地点以外の値は∞で初期化
    node[0] = 0     #スタートは0で初期化

    node_name = []
    heapq.heappush(node_name, [0, [0]])

    while len(node_name) > 0:
        #ヒープから取り出し
        _, min_point = heapq.heappop(node_name)
        last = min_point[-1]
        if last == Goal:
            return min_point, node  #道順とコストを出力させている
        
        #経路の要素を各変数に格納することで，視覚的に見やすくする
        for factor in edges[last]:
            goal = factor[0]   #終点
            cost  = factor[1]   #コスト

            #更新条件
            if node[last] + cost < node[goal]:
                node[goal] = node[last] + cost     #更新
                #ヒープに登録
                heapq.heappush(node_name, [node[last] + cost, min_point + [goal]])

    return []

if __name__ == '__main__':
    Edges = [
        [[1, 4], [2, 3]],             # ← 頂点Aからの辺のリスト
        [[2, 1], [3, 1], [4, 5]],   # ← 頂点Bからの辺のリスト
        [[5, 2]],                       # ← 頂点Cからの辺のリスト
        [[4, 3]],                       # ← 頂点Dからの辺のリスト
        [[6, 2]],                       # ← 頂点Eからの辺のリスト
        [[4, 1], [6, 4]],             # ← 頂点Fからの辺のリスト
        []                                # ← 頂点Gからの辺のリスト
        ]
    
    #今の目的地の数は7つ（0~6: A~G）
    node_num = 7
    Goal = 6    
    opt_root, opt_cost = dijkstra(Edges, node_num, Goal)    #道順とコストを出力させている

    #出力を見やすく整理するための変換用辞書型リストの作成
    root_converter = {}
    cost_converter = {}
    for i in range(node_num):
        root_converter[i] = chr(ord('A') + i)
        cost_converter[i] = opt_cost[i]
    
    arrow = " → "
    result = ""
    for i in range(len(opt_root)):
        if i > 0:
            result += arrow
        result += f"{root_converter[opt_root[i]]}({cost_converter[opt_root[i]]})"
        
    print(f"ノード(そこまでのコスト)\n\n{result}")

出力

ノード(そこまでのコスト)

A(0) → C(3) → F(5) → E(6) → G(8)

はじめの図で示した通り，A→C→F→E→Gが最短経路であると計算することができた．

感想

いよいよ実用っぽくなってきて，問題もますます面白くなってきた．こうなってくると以下に出力結果をうまく見せようかとも考えてくる．今回は，特に経路を示した３つ目の実装の出力は少し関数の出力も変えてコストも同時に表示できるように工夫した．アルゴリズム自体も，図で一通り説明できるくらいには理解できている．次のアルゴリズムも楽しみである．

参考文献

Pythonで始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　 増井 敏克　著　　翔泳社