スタート位置とゴール位置があり、そこに向かうルートが複数あるものとします。この中で、一番短い距離でゴールに到達する道のりを見つけ出す問題を、最短経路問題と呼びます。ダイクストラ法とは、それを見つけ出す手法の一つです。ルート検索アプリなどを作成する場合に必要となる、大変重要な手法です。
おまじないを書いておきます。
import numpy as np
import itertools as it
from graphviz import Graph
import random as rn
import time as ti
まずは、どのような問題を扱うのかを明確にするため、隣接行列を定義します。対角成分を0にすること、対称行列になることを間違えないようにしましょう。
# 隣接行列の定義
g_matrix = np.array([
[0, 1, 9, 2, 0, 0, 0, 12], # 0行目
[1, 0, 0, 0, 5, 8, 0, 0], # 1行目
[9, 0, 0, 0, 0, 2, 3, 10], # 2行目
[2, 0, 0, 0, 0, 0, 5, 0], # 3行目
[0, 5, 0, 0, 0, 1, 0, 0], # 4行目
[0, 8, 2, 0, 1, 0, 0, 6], # 5行目
[0, 0, 3, 5, 0, 0, 0, 2], # 6行目
[12, 0, 10, 0, 0, 6, 2, 0] # 7行目
])
er_flag = 0
# 対角成分チェック
for i in range(len(g_matrix)):
if g_matrix[i, i] != 0:
print("対角成分がすべて0になっていません。")
er_flag = 1
# 対称性チェック
if np.sum(g_matrix == g_matrix.T) != len(g_matrix)**2:
print("対称行列ではありません。")
er_flag = 1
# 最終評価
if er_flag == 0:
print("適切な隣接行列です。")
else:
print("不適切な隣接行列です。作り直してください。")
ノード名が数字だとわかりにくいので、下記のようにします。
ここで、$n+1$はノードの最大数です（0スタートなので、1を足します）。また、
とします。一番最初のノードからスタートし、最後のノードに到達することを目的とすることを意味します。この条件のもと、隣接行列をグラフで表現します。可視化を行う関数は以下の通りです。
def graph_view(matrix):
# ノード名生成
node_name = []
size = len(matrix)
for i in range(size):
node_name.append("s"+str(i))
# エッジを生成するノードの組み合わせ
comb_seed = np.arange(0, size)
comb = list(it.combinations(comb_seed, 2))
#print("エッジ生成ノードのリスト:", comb)
# グラフ作成
nG = Graph(format="pdf", engine="dot") # レイアウト: dot, fdp, osage, sfdp など
nG.attr("node", shape="circle", color="black", size="100")
for i in range(len(comb)):
if matrix[comb[i][0], comb[i][1]] > 0: # 距離が0以上のエッジのみ描画
nG.edge(node_name[comb[i][0]], node_name[comb[i][1]], label=str(int(g_matrix[comb[i][0], comb[i][1]])))
nG.node(node_name[0], shape="circle", color="blue", penwidth="2") # 始点
nG.node(node_name[-1], shape="circle", style="dashed", color="red", penwidth="2") # 終点
# 描画
nG.render("ngraphs")
display(nG)
関数を使用するには、隣接行列を与えればokです。
graph_view(g_matrix)
ノード（円）が場所で、エッジ（線）が移動可能であること、エッジに付与された数字が移動距離を表します。
続いて、上のグラフにおいて、ダイクストラ法により最短距離を求める方法を説明します。ダイクストラ法とは、始点に近いノードから最短距離を逐次求めていくアルゴリズムとなります。これは以下の手続きにより構成されます。用語がわからない場合は、本ページの冒頭を見直してください。
まずは、以下の表を用意します。$s_n$は終点ですから、ノードの数だけ列数があることになります。
| ノード | $s_0$ | $s_1$ | ... | $s_n$ |
|---|---|---|---|---|
| 最短距離 | xxx | xxx | ... | xxx |
| 暫定距離 | xxx | xxx | ... | xxx |
| 経路情報 | xxx | xxx | ... | xxx |
はじめに行う処理：
その後の処理：
経路を得る方法：
これを関数化したものが以下となります。
# 隣接行列、printフラグを入力 → 最短経路を出力
def dijkstra(matrix, print_flag):
t1 = ti.time()
# ノード数とノード名取得
node_name = []
size = len(g_matrix)
for i in range(size):
node_name.append("s"+str(i))
# はじめの処理
m = 1000 # 無限大的な数字
dist_temp = np.zeros(size) + m # 暫定距離
dist_opt = np.zeros(size) + m # 最短距離
dist_temp[0] = 0 # 始点のノードの暫定距離を0とする
pre_node_info = np.zeros(size) - 1
for t in range(size):
if print_flag == 1:
print("step: ", t)
# 手続き1
best_node = np.argmin(dist_temp) # 暫定距離が最も小さいものを s' に
dist_opt[best_node] = dist_temp[best_node] # s' の暫定距離を s' の最短距離に
if print_flag == 1:
print("・", node_name[best_node], "が暫定距離の中で最も小さいノードでしたので、この値を最短距離として採択しました。")
print("・（変更後）最短距離", dist_opt)
# 手続き2
if node_name[best_node] == node_name[-1]: # s' が 終点ならば終了
if print_flag == 1:
print("\n ### 最短経路が求まったので、処理を終了します ### ")
print("・最短距離", dist_opt)
print("・経路情報", pre_node_info)
### 出力 ###
route =["s"+str(size-1)]
pre_node_id = -1
while(pre_node_id != 0): # 終点から始点まで逆順に辿る
pre_node_id = int(pre_node_info[pre_node_id])
route.append("s" + str(pre_node_id))
tx = route[-1]
for i in range(2, len(route)+1):
tx = tx + " → " + route[-(i)]
print("・最短経路", tx, ",（距離 =", dist_opt[-1], "）")
t2 = ti.time()
elaps = t2-t1
print("・所要時間", np.round(elaps, 5), "秒")
break
if t == size - 1: # 反復が最大の場合も終了（何かのミスにより、無限ループを回避するため）
if print_flag == 1:
print("\n ### 最大反復回数になったので、処理を終了します ###")
break
# 手続き3
for i in range(size):
if matrix[best_node][i] > 0: # 直接接続されているノードであり、
if dist_opt[i] == m: # かつ、最短距離が無限大ならば、
# 手続き4
dist_check = dist_opt[best_node] + matrix[best_node, i] # 始点からs' への最短距離 + s'からs'と直接接続にあるノードへの距離
if dist_check < dist_temp[i]:
if print_flag == 1:
print("・", node_name[best_node],
"と直接接続されており、最短距離が記入されておらず、書き換え対象になったノードは",
node_name[i], "でした。")
dist_temp[i] = dist_check # 暫定距離を更新
pre_node_info[i] = best_node # 経路情報に s' を記載
if print_flag == 1:
print("・（変更後）暫定距離", dist_temp)
print("・（変更後）経路情報", pre_node_info, "\n")
dist_temp[best_node] = m
return [tx, elaps]
続いて、この関数を利用します。隣接行列とprint_flagを入力して使用します。計算過程を見たい場合はprint_flagを1に、見たくない場合は0にしてください。
res = dijkstra(g_matrix, print_flag = 1)
最短距離は、始点から$s_0$〜$s_7$までの最短経路の距離を意味します。最短距離となる経路は、「最短経路」に記載しています。 また、とても高速に解けることも確認できます。
ランダムにひたすら隣接行列を作って、最短経路を出すプログラムです。いくつか単純すぎる問題もありますが、自動生成しているためですので、気にしないでください。
for i in range(10):
print("\n ### Graph: ", i ," ###")
rn.seed(i)
# 隣接行列のランダム生成
size = rn.randint(10, 20)
g_matrix = np.zeros([size, size])
comb_seed = np.arange(0, size)
comb = list(it.combinations(comb_seed, 2))
for i in range(len(comb)):
sic = rn.random()
if sic < 0.20: # 20%の確率で経路生成
val = rn.randint(1, 10)
g_matrix[comb[i][0], comb[i][1]] = val # 対称行列に
g_matrix[comb[i][1], comb[i][0]] = val
else:
g_matrix[comb[i][0], comb[i][1]] = 0 # 対称行列に
g_matrix[comb[i][1], comb[i][0]] = 0
g_matrix[0, size-1], g_matrix[size-1, 0] = 10**2, 10**2 # 解なしを回避（無限大m=1000よりも小さく）
graph_view(g_matrix)
res = dijkstra(g_matrix, print_flag = 0)
ランダムにひたすら隣接行列を作って、最短経路を出すプログラムです。こちらも単純すぎる問題がいくつか含まれますが、気にせずお願いします。
for i in range(10):
print("\n ### Graph: ", i ," ###")
rn.seed(i)
# 隣接行列のランダム生成
size = rn.randint(30, 40)
g_matrix = np.zeros([size, size])
comb_seed = np.arange(0, size)
comb = list(it.combinations(comb_seed, 2))
for i in range(len(comb)):
sic = rn.random()
if sic < 0.10: # 10%の確率で経路生成
val = rn.randint(1, 10)
g_matrix[comb[i][0], comb[i][1]] = val # 対称行列に
g_matrix[comb[i][1], comb[i][0]] = val
else:
g_matrix[comb[i][0], comb[i][1]] = 0 # 対称行列に
g_matrix[comb[i][1], comb[i][0]] = 0
g_matrix[0, size-1], g_matrix[size-1, 0] = 10**2, 10**2 # 解なしを回避（無限大m=1000よりも小さく）
graph_view(g_matrix)
res = dijkstra(g_matrix, print_flag = 0)