ダイクストラ法(最短経路問題)

ダイクストラ法

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

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

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

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

[グラフ]

ソースコード

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

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

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

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

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

[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 であることを導き出すことができました。