アルゴリズムクイックリファレンスで2点間の最短ルートを求める「ダイクストラ法」について勉強したのでまとめます。

参考ドキュメントはこちらです。ウルトラ参考になりました。

 

応用的には飛行機の最短経路、電車の最短ルートの検索、カーナビとかの経路探索にも使われているアルゴリズムだろう。日常的におせわになっているアルゴリズムと言っても過言ではない。

ダイクストラ法（単一始点の最短経路アルゴリズム）

今回解く問題は以下の問題です。参考サイトに一つノードを加えました。

開始点（スタート）は1、終了点（ゴール）は6。上の図のような重み（距離）が与えられているときの1→6の最短経路を解きます。

ダイクストラ法の解説

ここでは一般的な説明ではなく、上記の解法の説明をします。いきなり一般論を述べるより具体的な問題から入った方が後のアルゴリズムも理解しやすいかと思います。

1. スタート地点を１番とする（当然）
2. 地点1から地点（2と3）に移動できるので、地点2と3の重みを更新します。（まだ地点2と地点3への最短経路は決定していません）
3. 番号の小さい方（ここでは2）に移動します。（これが初めての移動なので、地点2への最短経路は1→2で決定です）
4. 地点2から移動できる地点（3,4,6）があるので、重みを更新します。
5. 3,4,6のうち最小番号の3に移動します。
6. すでに3には1→3の重み80が存在しますが、今辿ってきた経路1→2→3が70なのでこちらの方が近いということになります。なので3の重みを70で更新します。とりあえずここまでの状態を図に示します。決定項目（最短経路）が青で未決定（現状では決定できない）事項が黄緑です。
7. 最初の図に戻ります。地点3から移動できるのは4と5なので、重みを更新します。そうすると今回の経路（1→2→3→4）での重みは70＋10=80ですが、すでにある経路（1→2→4）の方が重みが小さいのでこちらが最短経路ということになります。なので今回は重みは更新しません。
8. そして3から移動できる最小番号(地点4)に行きます。
9. 地点4から移動できるのは5と6です。今回の経路（1→2→3→4）の重みで更新すると、地点5での重みは4→5が30なので95、地点6での重みは4→6が10なので75となります。現時点での仮の経路は以下です。
10. この時点で最小経路は(1→2→4 →6)となるのが自明なのですが、練習のため最後までやりましょう。地点4からいける最小番号は5なので、地点5に移動。
11. 地点5はこれが初めての重みなので95で更新する。地点５から移動できる地点は地点6のみ。今回の経路（1→2→4→5）で重みを更新すると5→6が15なので95+15で110となる。すでにある経路（1→2→4→6）の重みが75なので今回は更新されずに最短経路が1→2→4→6で決定する。

このような解き方がダイクストラ法です。別名「貪欲法」と言います。残っている値（この場合は接点の数）が最小のものを選ぶという意味で貪欲です。なおダイクストラ法は重みが非負数の場合のみ使えます。非負数の場合はベルマン-フォード法を用います。これについては別途説明します。

コードを書いてみる

全体をいくつかの部分に分けて説明します。

---

隣接行列を定義します。隣接行列についてはこちらを参考にしてください。ここでは2重リストを用いて隣接行列の成分を表しています。

接点数をlen()関数で定義しています。未探索の接点をlist(range(node_num))で定義。これで未探索接点の初期条件（0,1,2,3,4,5）を設定します。

[math.inf]は正の無限大を表すので全ての接点の初期距離を∞（到着可能か不明）とする。

移動前の接点を[-1]*node_numで定義します。

接点0までの距離は開始点なので0とする。

---

次に最小のインデックス番号を取得する部分の関数です。

接点番号の初期値は0なのでstart = 0

indexに未探索ノード（ある地点から移動できる点）がある場合、index (接点)はそのまま。移動できる点がなくなった場合（接点1の場合2も3も計算した場合）、もうないのでelseとなり次の接点番号2へ移る。

---

ここはダイクストラ法の根本部分です。

while文は未探索接点がなくなるまで繰り返します（len(unserched_nodes) !=0）

最初の接点間の重みは無限大（math.inf）と定義する。ここから、上記で説明した1番にたどり着く（プログラミングは前提条件与えるのにやっとですね笑）

for文は未探索ノードにおけるループです。posible_min_distance=distance[node_index]の部分で最短距離が小さければ更新します。

そして先ほど説明したget_target_min_index関数で接点から次の接点へ移動する際の最小番号を更新する。（移動できる場合は更新せずにそのまま）

そして、この点は探索終了なので未探索接点（unserched_node）から削除する（remove(target_min_index)）

経路の重み計算にはその時の接点番号を用いる（ターゲットから伸びる接点）のでtarget_edgeとして定義する。

そしてif文内で過去に更新した重み（距離）よりも小さければ（重みが少なければ）それをdistance[index]として更新する。

最後に一つ前の接点に到達する接点のリストを更新する。

---

正直ここが全然わかりません。

previous_nodeとprevious_nodesの違いがいまいち。二行目のnode_num-1もなんの意味が。

node_numは接点数のはず。接点数は一定で6-1で5のはず。そしたらelse文とか意味ないじゃんて思ってしまう。

難しい。

実行結果

上で手計算で解いた時と同じ結果になります。しかし自分で0から書いたコードではないので、どこで何が起きているのか不明です。まさにブラックボックスの状態ですね。

以上、一応ダイクストラ法のアルゴリズムについて勉強してみましたがやはりコードに落としこむことができないm(_ _)m

今回はオライリーの「アルゴリズムクイックリファレンス」とgoogle先生を頼りに勉強しました。

正直この本は初心者には嫌われてますが、これを理解するための入門書チラ見しながらとかgoogle先生に聞きながらなら、かろうじて読めるかなと行ったところ。論文読んでるような感じです。時間はかかるけど、しっかり理解しながら読めば気付いた時にはそこらへんの入門書程度なら余裕だなって感じの知識はつきます。

たまには難しめの本から入りたいという変わり者にはおすすめです。

スポンサードリンク