ダイクストラ法による路線図最短経路解法(Pythonサンプルコード)

paizaでPythonを学ぼう
スポンサーリンク

はじめに

早稲田大学の早水桃子先生による動画講義「離散数学入門#5: 最短経路問題:ダイクストラ法とワーシャル–フロイド法」で使われている路線図をそのまま使って、最短経路を求めるアルゴリズムをPython上で動かすためのサンプルコードを解説する。

この記事の文責は私自身にある。内容に問題があった場合は私宛に連絡して頂きたい(元動画の作成者に問い合わせる人が出てくると迷惑がかかるので)。このコードは期待通りに動作する一例に過ぎず、洗練された最適解というわけではない。プログラミングの都合上、動画の解説通りのロジックではない箇所がある(気がする)。

なんとなく雰囲気が分かれば良いなら適当に読んで貰えば良いのだが、paizaの動画講座「Python3入門編」ぐらいの知識があると理解の助けになるだろう。私自身がプログラミング独学の初心者なので用語の使い方が怪しかったりするがご容赦頂きたい。

なお、paizaラーニングに「最小の運賃」という練習問題があり、その形式をなぞった形で数値(標準入力)を取得する。そちらの問題の解答は別記事を用意してある。

手元にPythonを動かす環境が無い人のために、オンライン上で動作確認するための仕組み(paiza.IO)を記事の最後に用意しておく。出発地点と終点を変更したり、枝の設定を変更したりして実際に動作を確認することが出来る。プログラミング知識がゼロの人でも「へー。そんなもんか」ぐらいの感覚は味わえるかもしれない。

動画の内容が前提になるのでこのページ上で動画が再生出来るよう動画を埋め込んでおく。

コードの解説

基本方針

東京とか品川という文字列では扱いづらいので、各駅を数値に置換する。具体的には東京=0、品川=1、渋谷=2、新宿=3、新横浜=4、横浜=5、小田原=6という形である。

1行目はスタート地点(start, s)の0と終点(target, t)の6。2行目は辺(edge, e)の個数13と頂点(vertex, v)の個数7。3行目以降は枝の情報で各頂点の位置とコストを表している。例えば「0 1 8」は東京から品川への移動コストが8であることを意味する。最終行の「5 6 52」は横浜・小田原間の移動を表している。標準入力で渡される値は次のような形になる。

0 6
13 7
0 1 8
0 2 16
0 3 15
1 2 13
1 3 21
1 4 10
1 5 17
2 4 27
2 6 78
3 5 33
4 5 13
4 6 15
5 6 52

ここでgという7*7(頂点数*頂点数)の二重リストを作り、各頂点間の移動コストをマトリクスで表現し直す。移動できない箇所は’NA’で表す。具体的には以下のような形になる。

[‘NA’, 8, 16, 15, ‘NA’, ‘NA’, ‘NA’]
[8, ‘NA’, 13, 21, 10, 17, ‘NA’]
[16, 13, ‘NA’, ‘NA’, 27, ‘NA’, 78]
[15, 21, ‘NA’, ‘NA’, ‘NA’, 33, ‘NA’]
[‘NA’, 10, 27, ‘NA’, ‘NA’, 13, 15]
[‘NA’, 17, ‘NA’, 33, 13, ‘NA’, 52]
[‘NA’, ‘NA’, 78, ‘NA’, 15, 52, ‘NA’]

標準入力からこの形を作るためのコードは以下の通り。

s, t = map(int, input().split())
e, v = map(int, input().split())
g = ['NA' * v for _ in range(v)] # 全て'NA'の2重リストgを作る

for _ in range(e): # 二重リストgのうち連結している箇所を上書きする
    tmp1, tmp2, tmp3 = map(int, input().split())
    g[tmp1][tmp2] = tmp3
    g[tmp2][tmp1] = tmp3

クラスの定義

ここからは以前に書いた記事と基本的に同じである。探索キューを管理するために次のようなClassを定義する。nodeは現在地を、costは経路の総コストを表す。heapqはコストの低い順に探索するために使うPython標準ライブラリ。__lt__は特殊メソッドと呼ばれるもので、大小比較の際に比べる値を定義し直している(多分)。heapqや特殊メソッドの詳しい説明は検索で調べて欲しい。

ダイクストラ法

各頂点への最安コストはtotal_costsで管理する。最初は全て未探索なので無限大=float(‘int’)をいれておき、探索した時にその値よりも低ければ上書きしていく。未探索キューはopen_que、探索済みはclosed_queに入れる。

open_queが空になるまでwhileループを回す。別の問題でグリッドを探索する時は上右下左の4方向だったが、この問題では全て頂点を多重リストgの中で探索している。連結していない場合は文字列’NA’が入っているのでループをスキップする。探索した地点に到達した際、それ以前の経路総コストより高ければループをスキップするが、安ければtotal_costの値を上書きする。

heapq(優先度付きキュー)を使うことで、常に経路の総コストが一番安い頂点を探索することになる。これは動画の13:00辺りにある「ラベルが未確定の頂点の中で最善の頂点を訪問する」という箇所に相当する。

最後にtotal_costからt(終点)の値をreturnで返す。

import heapq

def dijkstra():
    total_costs = [float('inf') for _ in range(v)]
    open_que = []
    closed_que = set()
    state = State(s, 0)  # node,cost
    heapq.heappush(open_que, state)

    while len(open_que) > 0:
        state = heapq.heappop(open_que)
        if state in closed_que:
            continue
        closed_que.add(state)

        for i in range(v):
            if g[i][state.node] == 'NA': # 連結していない場合はループをスキップ
                continue
            next_cost = state.cost + g[state.node][i]
            if total_costs[i] <= next_cost:
                continue
            total_costs[i] = next_cost
            heapq.heappush(open_que, State(i, next_cost))

    return total_costs[t]

コード全体

import heapq


class State:
    def __init__(self, node, cost):
        self.node = node
        self.cost = cost

    def __lt__(self, state):
        return self.cost < state.cost


def dijkstra():
    total_costs = [float('inf') for _ in range(v)]
    open_que = []
    closed_que = set()
    state = State(s, 0)  # node,cost
    heapq.heappush(open_que, state)

    while len(open_que) > 0:
        state = heapq.heappop(open_que)
        if state in closed_que:
            continue
        closed_que.add(state)

        for i in range(v):
            if g[i][state.node] == 'NA':
                continue
            next_cost = state.cost + g[state.node][i]
            if total_costs[i] <= next_cost:
                continue
            total_costs[i] = next_cost
            heapq.heappush(open_que, State(i, next_cost))

    return total_costs[t]


s, t = map(int, input().split())
e, v = map(int, input().split())
g = [['NA'] * v for _ in range(v)]

for _ in range(e):
    tmp1, tmp2, tmp3 = map(int, input().split())
    g[tmp1][tmp2] = tmp3
    g[tmp2][tmp1] = tmp3

answer = dijkstra()
print(answer)

オンライン上でのアルゴリズム動作確認

paiza.IOというオンライン上でコードを動かすサービスがあるので、その埋め込み機能を使ってみる。上段タブにはコードが、下段タブには標準入力の値が入っているので、デフォルトのまま実行ボタンを押せば下段タブの出力に「33」と出てくるはず。

下段にある入力タブの値を変更すれば、スタート地点と終了地点や枝の数や重さを動かすことが出来る。例えば入力タブ1行目の「0 6」を「1 5」にすれば品川・横浜間の最安コストを計算することが出来る。

また、(1行目はデフォルトのままで)3行目の「0 1 8」を「0 6 1」に変えれば、東京から小田原への1分の直通ルートが存在することを意味し、実行ボタンを押すと「1」が出力される。あるいは、3行目を「0 6 99」とすれば、直通ルートは存在するが99分かかることになり、最短ルートの計算結果は54分になる。これは東京・品川ルートを上書きで消したためで、東京・渋谷・品川・新横浜・小田原ルートの合計値が出てくる。

大きな画面で表示させたい場合はこのリンクをクリックすればブラウザの別タブが開く。閲覧環境等で埋め込みが上手く動作していない場合も別タブで表示してご確認頂きたい。(ちなみに自分の環境ではブラウザの横幅をグリグリ調整すると表示が直った。)

コメント

タイトルとURLをコピーしました