Dijkstraのアルゴリズムは、グラフのノード間の最短経路を見つけるために設計されたものである。
1956年にオランダのコンピュータ科学者Edsger Wybe Dijkstraが、ロッテルダムからフローニンゲンまでの最短経路を考え、設計した。
その3年後に発表された。
注：ダイクストラのアルゴリズムは、長い年月の間に変化があり、様々なバージョンやバリエーションが存在する。
元々は、2つのノード間の最短経路を計算するために使用されていた。
その仕組みから、あるノードとグラフ内の他のすべてのノードとの間の最短経路を計算するように適応された。
このようにして、2つのノード間の最短経路と、それ以外のすべてのノードからなる最短経路樹を作成することができます。
その後、興味のない木を切り捨てて、2つのノード間の最短経路を得ることができますが、どうしても木全体を計算しなければならず、これがダイクストラのアルゴリズムの欠点で、大きなグラフには不向きなのです。
レッスンでは、後者の実装を中心に説明します。
>
> このレッスンでは、ダイクストラのアルゴリズムとその背後にある直感を理解した上で、Pythonで実装していきます。
ダイクストラのアルゴリズム – 理論と直感
ダイクストラのアルゴリズムは、無向の連結重み付きグラフで動作する。
はじめに、正しい最短経路を割り当てられたすべての頂点を追跡するために、訪問済み頂点のセットを作成したい。
また、グラフ内のすべての頂点の「コスト」（その頂点に至る現在の最短パスの長さ）を設定する必要がある。
すべてのコストは、最初に「無限大」に設定される。
これは、比較する他のすべてのコストが、最初のコストより小さくなるようにするためである。
唯一の例外は、最初の頂点のコストです。
この頂点は、ノード s としてマークされ、それ自身へのパスを持たないので、コストは0になります。
そして、グラフを縦断するまで（最短経路が割り当てられていない頂点が存在する限り）、主に2つのステップを繰り返します。
- 現在のコストが最短の頂点を選び，それを訪問し，訪問済み頂点集合に追加する．
- その隣接する頂点のうち、まだ訪問していない頂点のコストを全て更新する。n
とmの間の辺で、mが未訪問の場合 -cheapestPath(s, n)+cheapestPath(n,m)<cheapestPath(s,m)なら、sとm間の最も安いパスをcheapestPath(s,n)+cheapestPath(n,m)` と同じ値に更新する。
これは少し理解しにくいかもしれないので、実装する前にプロセスを可視化してみましょう。
ここに無向の重み付き連結グラフがあります。
頂点0が出発点だとしよう。
このグラフの頂点の初期コストは、開始点を除いて無限大に設定することにします。
| 頂点0から頂点0に到達するためのコスト
| — | — |
| 0 | 0 |
| 1 | inf
| 2｜inf｜（インフ
| 3｜inf｜（インフ
| 4 | inf
| 5｜inf｜（インフ
| 6 | inf
| 7 | inf
| 8｜inf｜（インフ
コストが最小の頂点を選びます – これが頂点0です。
これを訪問済みとしてマークし、訪問済み頂点の集合に追加する。
開始ノードは常に最小のコストを持つので、常に最初に追加されることになる。
次に、隣接する頂点(1, 6)のコストを更新する。
0 + 4 < infinityと0 + 7 < infinity`なので、これらの頂点へのコストを更新します。
| 頂点0から頂点に到達するためのコスト
| — | — |
| 0 | 0 |
| 1 | 4 |
| 2 | inf
| 3｜inf｜（インフ
| 4 インフルエンザ
| 5｜inf｜（インフ
| 6 | 7 |
| 7｜inf｜（インフ
| 8｜inf｜（インフ
ここで、次にコストの小さい頂点を訪ねます。
4の重みは7より小さいので、頂点1へトラバースする。
頂点1: 偽グタ 破断後、訪問済みとしてマークし、隣接する頂点を観測・更新する。
2, 6, 7 を観察し、更新する。
- 4 + 9 < infinity` なので、頂点 2 の新しいコストは 13 になります。
- 4 + 11 > 7` なので、頂点 6 のコストは 7 のままです。
- 4 + 20 < infinity` なので、頂点 7 の新しいコストは 24 になります。
これが新しいコストです。
| 頂点0から頂点6への移動コスト
| — | — |
| 0 | 0 |
| 1 | 4 |
| 4｜inf
| 5｜インフ
| 6 | 7 |
| 7 | 24 |
| 8｜inf｜（インフ
次に訪問する頂点は頂点6です。
これを訪問済みとし、その隣接頂点のコストを更新する。
| 頂点0から頂点6に到達するためのコスト
| — | — |
| 0 | 0 |
| 1 | 4 |
| 4｜inf
| 5｜インフ
| 6 | 7 |
| 7 | 8 |
| 8｜inf｜（インフ
頂点7まで処理を継続する。
| 頂点0から頂点7に到達するためのコスト
| — | — |
| 0 | 0 |
| 3｜インフ
| 4 | 9 |
| 5｜インフ
| 6 | 7 |
| 7 | 8 |
| 8 | 11 |
そして再び、頂点4へ。
| 頂点0から頂点4への移動コスト
| — | — |
| 0 | 0 |
| 1 | 4 |
| 4 | 9 |
| 5 | 24 |
| 6 | 7 |
| 8 | 11 |
そして再び、頂点2へ。
これから考える頂点は頂点3だけです。
11 + 6 < 19`なので、頂点3のコストが更新されます。
そして、頂点8へ進みます。
最後に、頂点5を更新します。
| 頂点0からそこへ行くための｜頂点｜コスト｜を更新します。
| 8 | 11 |
最後にループ状の構造の頂点を更新しましたので、あとはそれをトラバースするだけです – まず頂点3まで。
そして最後に、頂点5へ。
もう、更新が必要な未訪問の頂点はない。
最終的なコストは、ノード0からグラフの他のすべてのノードへの最短経路を表している。
| 頂点0からそこへ到達するためのコスト
| — | — |
| 0 | 0 |
| 1 | 4 |
| 2 | 11 |
| 3 | 17 |
| 4 | 9 |
| 5 | 24 |
| 6 | 7 |
| 8 | 11 |
このテーブルをプルーニングして、 *Node X と *Node Y の間の距離だけを残すこともできますが、いずれにせよこの計算を実行しなければならないので、計算コストはあまり削減されないでしょう。
Pythonによるダイクストラアルゴリズムの実装
さて、ここまででステップバイステップのプロセスを確認したので、PythonでどのようにDijkstraのアルゴリズムを実装するか見てみましょう まだ訪れていない頂点をソートして記録するために、PriorityQueueを使用します。
from queue import PriorityQueue
では、Graphというクラスのコンストラクタを実装してみましょう。
class Graph:
def __init__(self, num_of_vertices):
self.v = num_of_vertices
self.edges = [[-1 for i in range(num_of_vertices)] for j in range(num_of_vertices)]
self.visited = []
この単純なパラメタライズドコンストラクタでは、頂点の数を指定します。
時間的複雑性
このアルゴリズムでは、各エッジを1回ずつ通過させるので、時間計算量は O(|E|) となる（|E| はエッジの数を表す）。
また、各ノードを1回ずつ訪問するため、時間計算量は O(|V|) となる（ここで |V| は頂点の個数を表す）。
各頂点は優先キューに入れられ、次に近い頂点を見つけるのに一定の時間 O(1) がかかることになります。
しかし、この優先度待ち行列の頂点をソートするために、 O(Vlog|V|) の時間を使用します。
この結果、このアルゴリズムの時間複雑度は O(|E|+|V|log|V|) となる。