ダイクストラ法（最短経路問題）

ダイクストラ法

ダイクストラ法 は、最短経路問題 を解くアルゴリズムの１つです。

ダイクストラ法 には次のような特徴があります。

  • コストが最小になる頂点 を探しながら最短経路を求める。
  • マイナスの値 の場合は使えないが、ベルマンフォード法よりも高速に解を求めることができる。

次のようなグラフを考えてみます。

[グラフ]

ソースコード

ソースコードでは、グラフの情報を次の入力例のように定義してみます。

  • 頂点は名前（頂点名）をもち、それぞれの頂点は隣の頂点情報(edge)と自分のコスト(cost)情報を持っています。
  • 隣の頂点情報は、頂点名（辞書型データのキー）とそこに移動するためのコスト（辞書型データのバリュー）があり、複数存在することがあります。
  • 頂点自体がもっているコストは、そこに辿りつくためのコストであり、初期値としてはスタート地点が０、それ以外は無限大を設定しておきます。

ダイクストラ法 では、コストが最もコストが小さくなる頂点 を選択することを繰り返して探索する方法です。

一度チェックしたした頂点は チェック済み として、チェックしていない頂点 の中からコストが最も小さいものを順番に確認していきます。

最も小さいコストの頂点が複数ある場合は、そのうちどれか１つを選択してチェックしていきます。

[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
#---------- 入力例 ----------
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までの最小コスト
}
#----------------------------
# ダイクストラ法（最もコストの小さい頂点を順番に確認していく方法）
while len(nodes):       # 未チェックの頂点がある限り実行
    # 最もコストが小さい頂点を探す
    min_cost = min([node_info['cost'] for src, node_info in nodes.items()])
    for name, node_info in nodes.items():
        if node_info['cost'] == min_cost:
            min_node_name = name    # 最もコストが小さい頂点名を取得
            break

    # 最もコストが小さい頂点からの辺を繰り返しチェックする
    for dst, cost in node_info['edge'].items():
        # 次の頂点が未チェック かつ 次の頂点までのコストが更新対象であれば更新
        if dst in nodes and nodes[dst]['cost'] > nodes[min_node_name]['cost'] + cost:
            nodes[dst]['cost'] = nodes[min_node_name]['cost'] + cost

    if min_node_name == 'Goal': # チェックした頂点が'Goal'の場合
        print('解：最小コストは', nodes['Goal']['cost'])    # 最小コストを表示して終了
        break

    del nodes[min_node_name]    # チェックが終わった頂点は削除(チェック済みとする)

[実行結果]

解：最小コストは 8

頂点Start から 頂点Goal までの最小コストは 8 であることを導き出すことができました。