AI&Julia #15｜グラフ理論 » 最短経路問題 » ダイクストラ法
はじめに
ダイクストラ法を使って「重み付き無向グラフ」を探索します。この探索結果を利用すると、どこにゴール地点を設定してもスタート地点からの最短経路を復元することができます。
ダイクストラ法は、カーナビゲーション，乗り換え案内，ルーティングプロトコルなどに応用されています。
グラフのデータ構造
図 1に「重み付き無向グラフ」を示します。無向グラフのエッジは見かけ上は 1本ですが、内部的には互いに逆向きの 2本のエッジで構成されます。
図 1 重み付き無向グラフ
エッジを定義
図 1のグラフには見かけ上のエッジが 12本あります。図右側のベクトルedgesはこの 12本のエッジの完全なリストです。この見かけ上のエッジを定義しているタプルの形式は
-
u -
v u -
w w≥0
例としてノードedgesの最初の 3要素そのものです。他のノードについても同じ要領でエッジを作成していくとエッジのリストを完成させることができます。この段階では逆向きのエッジについて考慮する必要がありません。
グラフを定義
ダイクストラ法では、注目ノードedgesはこの操作に適した構造になっていません。これを解決するデータ構造としてグラフを定義します。
この式は、注目ノード
先ほどのベクトルedgesをグラフに変換すると次のようになります。
5 => [(2, 2.0), (3, 4.0), (4, 2.0), (6, 1.0), (7, 4.0)]
4 => [(2, 5.0), (5, 2.0), (6, 6.0)]
6 => [(4, 6.0), (5, 1.0), (7, 2.0)]
7 => [(1, 9.0), (5, 4.0), (6, 2.0)]
2 => [(1, 4.0), (3, 1.0), (4, 5.0), (5, 2.0)]
3 => [(1, 2.0), (2, 1.0), (5, 4.0)]
1 => [(2, 4.0), (3, 2.0), (7, 9.0)]
ベクトルedgesの変換には自前で実装したcreate_graph関数を用います。その中で逆向きのエッジを追加する処理も行います。これにより、どのノード
ダイクストラ法のアルゴリズム
ダイクストラ法（Dijkstra's algorithm）は、毎回その時点で最良の選択を行う貪欲法（greedy algorithm）の 1つで、非負の重みを持つグラフについて単一始点最短経路問題を効率的に解くアルゴリズムです。ここでは、アルゴリズムのポイントを具体例を使って見ていきます。図 2に、図 1のグラフで探索を行った場合について、優先度付きキューと累積距離が変化する様子を示します。
図 2 優先度付きキューと累積距離
アルゴリズムのポイントは次の通りです。
- 優先度付きキューを活用することにより、最短経路として有望なノード
u u - グラフから注目ノード
u v v v - 優先度付きキューが空になったら探索を終了します。この時点で、すべてのノードについて、最短距離（最短経路での累積距離）が確定しています。
このアルゴリズムには明示していませんが、ダイクストラ法では最短経路木（Shortest Path Tree, SPT）を構築するのが容易です。最短経路木には、どのノードからでも最短経路でスタート地点に向かって遡上するのに必要な情報が記録されます。この情報を利用すると、どこにゴール地点を設定してもスタート地点からの最短経路を復元することができます。
実装例
実装は、核心部と可視化部の 2つに分けて掲載します。
核心部
核心部の主要な関数は次の通りです。
-
dijkstra関数 — ダイクストラ法により「重み付き無向グラフ」を探索します。 -
restore_path関数 — 最短経路木を利用して、スタート地点からゴール地点までの最短経路を復元します。 -
create_graph関数 — エッジの定義を元にグラフを作成します。
using DataStructures, CairoMakie, Printf
const Edge = Tuple{Int, Float64} # エッジ（隣接ノードと重みのペア）
const Adjac = Vector{Edge} # 隣接リスト
const Graph = Dict{Int, Adjac} # グラフ
const Dist = Dict{Int, Float64} # 累積距離（スタート地点から各ノードまでの累積距離）
const Prev = Dict{Int, Union{Nothing, Int}} # 最短経路木
# ダイクストラ法により「重み付き無向グラフ」を探索
function dijkstra(graph::Graph, start::Int)
pque = PriorityQueue{Int, Float64}() # 優先度付きキュー（累積距離が短い＝最優先）
dist = Dist(v => Inf for v in keys(graph)) # 累積距離
prev = Prev(v => nothing for v in keys(graph)) # 最短経路木
pque[start] = 0 # キューから最初に取り出されるのはスタート地点とする
dist[start] = 0 # スタート地点を最短距離（0）で初期化
while !isempty(pque)
u = dequeue!(pque) # キューから最短距離（最優先）のノードを取り出して注目ノードuとする
for (v, w) in graph[u]
alt = dist[u] + w # ノードvまでの新しい累積距離を計算
if alt < dist[v] # その結果がノードvの既知の累積距離よりも短ければ、
dist[v] = alt # ノードvを新しい累積距離に更新
pque[v] = alt # ノードvの優先度を上げる
prev[v] = u # ノードvから最短経路で遡上するにはノードuを経由するのが有望
end
end
end
dist, prev
end
# 最短経路木を利用して、スタート地点からゴール地点までの最短経路を復元
function restore_path(prev::Prev, goal::Int)
path = Int[] # 最短経路
v = goal # ゴール地点から遡上を開始
while v != nothing
pushfirst!(path, v) # 経由するノードを最短経路に記録
v = prev[v] # 遡上で経由するノードを取り出す
end
path
end
# エッジの定義を元にグラフを作成
function create_graph(edges)::Graph
nodes = unique([e[i] for e in edges for i in 1:2]) # ノードの一覧を作成
graph = Graph(v => Edge[] for v in nodes) # 隣接リストが空のグラフを作成
for (u, v, w) in edges
push!(graph[u], (v, w)) # 隣接リストにエッジを追加
push!(graph[v], (u, w)) # 隣接リストに向きが逆のエッジを追加
end
graph
end
可視化部
可視化部の主要な関数は次の通りです。
-
vis_path関数 — グラフ上に最短経路を可視化します。 -
show_dist関数 — すべてのノードについてスタート地点からの最短距離をテキストで表示します。 -
show_path関数 — 最短経路をテキストで表示します。
# グラフ上に最短経路を可視化
function vis_path(graph::Graph, dist::Dist, path::Vector{Int}, start::Int, goal::Int)
function inacircle() # ノードを円形配置するための座標を計算
n = length(graph) # ノードの数
θ = range(0, 2π, length=n+1)[1:n]
[(3*cos(angle), 3*sin(angle)) for angle in θ]
end
function plot_path(ax, pos) # 最短経路をプロット
coords = [pos[u] for u in path]
lines!(ax, coords, color=:blue, linewidth=4)
end
function plot_edges(ax, pos) # エッジと重みをプロット
for (u, adjac) in graph # 注目ノードuと隣接リストを順次処理するループ
for (v, w) in adjac # 隣接ノードvと重みw
u >= v && continue # 重複描画を避ける
x1, y1 = pos[u]
x2, y2 = pos[v]
lines!(ax, [x1,x2], [y1,y2], color=:gray65, linewidth=2)
midx = (x1 + x2) / 2
midy = (y1 + y2) / 2
text!(ax, midx, midy, text=string(Int(w)), fontsize=16, color=:black, align=(:center,:center)) # 重み
end
end
end
function plot_nodes(ax, pos) # ノードをプロット
for v in keys(graph)
x, y = pos[v]
if (v == start) color = :limegreen # スタート地点
elseif (v == goal) color = :firebrick1 # ゴール地点
elseif (v in path) color = :orange # 最短経路上のノード
else color = :lightblue # 最短経路外のノード
end
str_dist = string(Int(dist[v]))
scatter!(ax, x, y, color=color, markersize=30, strokewidth=1, strokecolor=:black) # ノードの色
text!(ax, x, y, text=string(v), fontsize=17, color=:black, align=(:center,:center)) # ノードの番号
text!(ax, x, y-0.3, text=str_dist, fontsize=14, color=:red, align=(:center,:center)) # 最短距離
end
end
fig = Figure(size=(500,500))
ax = Axis(fig[1,1], aspect=1)
pos = inacircle() # ノードを円形配置するための座標を計算
plot_path(ax, pos) # 最短経路をプロット
plot_edges(ax, pos) # エッジと重みをプロット
plot_nodes(ax, pos) # ノードをプロット
hidedecorations!(ax)
hidespines!(ax)
display(fig)
fig
end
# すべてのノードについてスタート地点からの最短距離をテキストで表示
function show_dist(dist::Dist, start::Int)
println("ノード $start から各ノードまでの最短距離:")
for (v, d) in sort(collect(dist), by=x->x[1])
println(" ノード $v: $(Int(d))")
end
end
# 最短経路をテキストで表示
function show_path(path::Vector{Int}, dist::Dist, start::Int, goal::Int)
println("最短経路: ", join(path, " ➝ "))
println("ノード $start からノード $goal までの最短距離: $(Int(dist[goal]))")
end
実行例
初期設定とグラフの探索を行ったあと、2箇所のゴール地点について最短経路を復元します。
初期設定とグラフの探索
エッジの定義を元にグラフを作成した後、ダイクストラ法によりグラフを探索します。そして、すべてのノードについてスタート地点からの最短距離をテキストで表示します。
# エッジを定義、各要素は (u, v, w) のタプル
edges = [
(1, 2, 4), (1, 3, 2), (1, 7, 9),
(2, 3, 1), (2, 4, 5), (2, 5, 2),
(3, 5, 4),
(4, 5, 2), (4, 6, 6),
(5, 6, 1), (5, 7, 4),
(6, 7, 2)
]
start = 1
graph = create_graph(edges) # エッジの定義を元にグラフを作成
dist, prev = dijkstra(graph, start) # ダイクストラ法により「重み付き無向グラフ」を探索
show_dist(dist, start) # すべてのノードについてスタート地点からの最短距離をテキストで表示
ノード 1 から各ノードまでの最短距離:
ノード 1: 0
ノード 2: 3
ノード 3: 2
ノード 4: 7
ノード 5: 5
ノード 6: 6
ノード 7: 8
最短経路を復元（1）
ゴール地点を 7に設定した場合の最短経路を復元します。
goal = 7
path = restore_path(prev, goal) # ゴール地点までの最短経路を復元
fig = vis_path(graph, dist, path, start, goal) # グラフ上に最短経路を可視化
show_path(path, dist, start, goal) # 最短経路をテキストで表示
save("15-goal=7.png", fig)
図 3 ゴール ⑦ までの最短経路
最短経路: 1 ➝ 3 ➝ 2 ➝ 5 ➝ 6 ➝ 7
ノード 1 からノード 7 までの最短距離: 8
最短経路を復元（2）
ゴール地点を 4に設定した場合の最短経路を復元します。
goal = 4
path = restore_path(prev, goal) # ゴール地点までの最短経路を復元
fig = vis_path(graph, dist, path, start, goal) # グラフ上に最短経路を可視化
show_path(path, dist, start, goal) # 最短経路をテキストで表示
save("15-goal=4.png", fig)
図 4 ゴール ④ までの最短経路
最短経路: 1 ➝ 3 ➝ 2 ➝ 5 ➝ 4
ノード 1 からノード 4 までの最短距離: 7
おわりに
グラフのデータ構造をしっかりと押さえてからダイクストラ法のアルゴリズムに進みました。今後、グラフニューラルネットワーク（GNN）に取り組むことがあれば、これが良い助走になってくれるものと期待しています。
Discussion