ダイクストラ法 Python & C++ （例）
サラ・チェン
⚡ スマートサマリー
ダイクストラ法は、負でない辺を持つ重み付きグラフにおいて、単一の始点頂点から他のすべての頂点への最短経路を計算します。この貪欲法は、 Google マップルーティング、OSPF IPルーティング、そして無数のネットワーク最短経路のユースケース。
最短経路または最短距離とは何ですか？
始点頂点から終点頂点までの経路のうち、コストが最小となる経路を最短経路または最短距離と呼びます。グラフ理論では、始点から終点まで複数の経路が存在する可能性があります。これらの経路の中で、コストが最小となる経路があれば、それを最短経路と呼びます。
ここでいう「コスト」とは、経路上のノード数、または各エッジのコストの合計を意味します。経路は1つまたは複数のエッジを持つことができます。2つの頂点間の接続を「エッジ」と呼びます。最短経路アルゴリズムには、ダイクストラ法やベルマン・フォード法など、さまざまな種類があります。
ここでは、ダイクストラ法について説明します。以下の重み付きグラフを見てみましょう。
無向重み付きグラフ
- 「重み付け」という用語は、あるノードから別のノードへ移動する際のコストを意味します。例えば、ノード1からノード2へ移動する場合、コスト（重み）は1です。
- ノード1とノード2の間の経路をエッジと呼びます。
- 「無方向」とは、あるノードから別のノードへ移動したり、前のノードに戻ったりできることを意味します。したがって、ノード1からノード7までのすべての経路を検索しようとすると、次のようになります。
| ルートまたはパス | 費用 |
|---|---|
| 1-2-6-7 | (1+3+3) = 7 |
| 1-2-3-7 | (1+9+1) = 11 |
| 1-3-7 | （7 + 1）= 8 |
| 1-4-5-7 | (6+2+5) = 13 |
これら4つのルートのうち、最初のルートのコストは7であることがわかります。したがって、コストの面ではこれが最短ルートです。
最短経路
ダイクストラのアルゴリズムの仕組み
ダイクストラ法は、有向グラフと無向グラフの両方において、最短距離を求めることができます。このアルゴリズムは、常に始点から最も近いノードを選択するため、「貪欲」なアルゴリズムと言えます。「貪欲」とは、複数の結果の中から最良の結果を選択することを意味します。
ここでは、他のすべての経路の中から最短経路を見つけようとしています。そのため、ダイクストラ法は単一の始点ノードからすべての最短経路を見つけます。結果として、それは 貪欲なアルゴリズム.
以下の「例」セクションでは、手順を追って説明します。手順は以下のとおりです。
ステップ1） 開始ノードのコストを0に初期化し、残りのノードのコストを無限大にする。
ステップ2） 配列またはリストを保持して trac訪問したノードのk個。
ステップ3） ノードのコストを最小コストに更新します。これは、現在のコストとパスのコストを比較することで実行できます（例のセクションで説明しています）。
ステップ4） すべてのノードを訪問するまで、ステップ3を続けます。
これらの手順をすべて完了すると、送信元から宛先までのコストが最小となるパスが見つかります。
ダイクストラとBFS、DFSの違い
ダイクストラ法とBFS-DFSの主な違いは、ダイクストラ法が最短経路探索アルゴリズムであるのに対し、BFSとDFSは一般的な経路探索アルゴリズムであるという点です。一般的に、BFSとDFSは経路探索時に辺のコストを考慮しません。そのため、これらのアルゴリズムは最短経路を保証することはできません。
BFSの動作原理を示す2Dグリッドデモンストレーション
アルゴスケッチBFSのデモンストレーション
このデモは、BFS がパスを検索するだけであることを示しています。 ただし、パスの重みは気にされません。 BFS (幅優先探索) は、あるノードから別のノードへの移動にかかるコストが 1 だけであると想定しています。
例としてグラフを見てみましょう。
ここでは、BFSはレベル2でパスを見つけます。BFSはレベル順にグラフを走査します。したがって、次のように移動します。
ステップ1） ノード「1」から開始し、隣接するノード2、3、4をすべて訪問します。
ステップ2） ノード2、3、4をレベル1としてマークし、それらの隣接ノードを訪問します。目的地ノードに到達するまで、すべての隣接ノードの探索を続けます。
DFS に関しては、次のように 1 から 7 までのパスをトラバースします。
- 1→2→3→7（オリジナルコスト10、DFSコスト3）
- 1→2→6→7（オリジナルコスト7、DFSコスト3）
- 1→3→7 (オリジナルコスト8、DFSコスト2)
- 1→4→5→7（オリジナルコスト13、DFSコスト3）
ご覧のとおり、DFSはエッジの数に基づいてパスコストを計算します。DFSは以下の処理を行います。
- DFS は、ソース (開始頂点) から宛先までのパスを見つけることができます。
- 発見されたソースノードから宛先までのパスが最短パスであるかどうかは保証できません。
しかし、ダイクストラ法においては、辺の選択はコストに基づいて行われます。貪欲法であるため、最小コストの経路を選択します。
ダイクストラのアルゴリズムの例
ダイクストラのアルゴリズムは、コストまたは重みを使用してパスの総コストを計算します。
ダイクストラのアルゴリズムの目標は、この総コストまたは重量を最小限に抑えることです。 上に示した例では、ノード 1 からノード 7 までの最適なパスを見つけて、すべてのコストを計算します。
ダイクストラ法では、重みを計算することで最短経路を見つけます。すべての経路を探索するわけではありません。ダイクストラ法を例を用いて説明しましょう。例えば、ノード1からノード7までの最短経路を見つけるように求められたとします。
このプロセスの手順は次のとおりです。
ステップ1） 開始ノードのコストを0に初期化します。 「インフ」 他のノードへ。これは、ソースとノードの間にパスが存在しないか、パスがまだ訪問されていないことを意味します。
ステップ2） ノード1を選択すると、訪問済みとしてマークされます。次に、ノード1に隣接するすべてのノードを更新します。2、3、4はノード1の隣接ノードです。
コストを更新するときは、次の手順に従う必要があります。
上記の式を使用して、各ノードのコストを更新できます。たとえば、ノード1にいて、隣接するノード2、3、4のコストを更新する必要があるとします。更新後のコストは次のようになります。
ステップ3） ノード「2」の隣接ノードは6と3です。ノード「6」のコストは、無限大（現在の値）とノード2のコスト＋2から6までのパスコストを比較することで更新されます。簡単に言うと、ノード「6」のコストは1＋3、つまり4になります。
ノード 3 はノード 2 の隣接ノードです。ただし、前の手順でそのコストを計算したところ、7 でした。ここで、パスが 1-2-3 の場合、ノード 3 のコストは 10 になります。パス 1-2- 3はコスト10、1～3はコスト7になります。
ステップ4） ノード3の隣接ノードは7です。そこで、ノード7の現在の値をパスコスト(7+1)または8と比較し、ノード7のコストを更新します。つまり、8です。したがって、ノード1からノード7へのパスは1→3→7となり、コストは8です。
ステップ5） ノード4については、隣接ノードのコストをそれに応じて更新します。したがって、ノード「5」のコストは8に更新されます。ステップ4と5の後、次のようになります。
さて、パス1-3-7のコストは（以前の）8です。ノード「7」は、ノード「6」からノード「7」に到達できるため、訪問済みとしてマークされていません。パス「1-2-6」のコストは4でした。したがって、パス1-2-6-7のコストは7になります。
7 < 8 なので、始点頂点「1」から終点頂点「7」への最短経路は 1-2-6-7 となり、コストは 7 です。以前は 1-3-7 で、コストは 8 でした。したがって、最終的なグラフは次のようになります。
黒い線でマークされたエッジは 1 から 7 までの最短パスであり、コストは 7 になります。
ニックネーム Code ダイクストラ法
ダイクストラ法の擬似コードは以下のとおりです。
Dijkstra(G, S): for each vertex V in G distance[V] <- Infinity previous[V] <- NULL if V does not equal S, then, (priority queue) Q.push(V) distance[S] = 0 While Q is not empty U <- Extract the MIN from Q For each unvisited adjacent V of U TotalDistance <- distance[U] + edge_cost(U, V) if TotalDistance is less than distance[V], then distance[V] <- TotalDistance previous[V] <- U return distance, previous
C++ ダイクストラ法の実装
ダイクストラのアルゴリズムを実装するには、 C++コードは以下のとおりです。
#include <bits/stdc++.h> using namespace std; #define size 7 int minimumDistance(int distance[], bool visited[]) { int min = INT_MAX; int min_index = INT_MAX; for (int i = 0; i < size; i++) { if (!visited[i] && distance[i] <= min) { min = distance[i]; min_index = i; } } return min_index; } void printParentPath(int parent[], int i) { if (parent[i] == -1) { return; } printParentPath(parent, parent[i]); cout << i + 1 << " "; } void dijkstra(int graph[size][size], int source) { int distance[size]; bool visited[size]; int parent[size]; for (int i = 0; i < size; i++) { parent[0] = -1; distance[i] = INT_MAX; visited[i] = false; } distance[source] = 0; for (int i = 0; i < size - 1; i++) { int U = minimumDistance(distance, visited); visited[U] = true; for (int j = 0; j < size; j++) { int curr_distance = distance[U] + graph[U][j]; if (!visited[j] && graph[U][j] && curr_distance < distance[j]) { parent[j] = U; distance[j] = curr_distance; } } } cout << "Vertex\t\tDistance\tPath" << endl; for (int i = 1; i < size; i++) { cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t" << source + 1 << " "; printParentPath(parent, i); cout << endl; } } int main() { int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0}, {7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0}, {0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3}, {0, 0, 0, 0, 5, 3, 0}}; dijkstra(graph, 0); }
出力：
Vertex Distance Path 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Python ダイクストラ法の実装
ダイクストラのアルゴリズムを実装するには、 Pythonコードは以下のとおりです。
num_of_vertex = 7 def minimumDistance(distance, visited): _min = 1e11 min_index = 1e11 for i in range(num_of_vertex): if not visited[i] and distance[i] <= _min: _min = distance[i] min_index = i return min_index def printParentNode(parent, i): if parent[i] == -1: return printParentNode(parent, parent[i]) print("{} ".format(i + 1), end="") def dijkstra(graph, src): distance = list() visited = list() parent = list() for i in range(num_of_vertex): parent.append(-1) distance.append(1e11) visited.append(False) distance[src] = 0 for i in range(num_of_vertex - 1): U = minimumDistance(distance, visited) visited[U] = True for j in range(num_of_vertex): curr_distance = distance[U] + graph[U][j] if not visited[j] and graph[U][j] and curr_distance < distance[j]: parent[j] = U distance[j] = curr_distance print("Vertex\t\tDistance\tPath") for i in range(num_of_vertex): print("{}->{}\t\t{}\t\t{} ".format(src + 1, i + 1, distance[i], src + 1), end="") printParentNode(parent, i) print("") graph = [ [0, 1, 7, 6, 0, 0, 0], [1, 0, 9, 0, 0, 3, 0], [7, 9, 0, 0, 0, 0, 1], [6, 0, 0, 0, 2, 0, 0], [0, 0, 0, 2, 0, 0, 0], [0, 3, 0, 0, 0, 0, 3], [0, 0, 0, 0, 5, 3, 0] ] dijkstra(graph, 0)
出力：
Vertex Distance Path 1->1 0 1 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
このアルゴリズムは、始点ノードからの最短距離を計算していることがわかります。
ダイクストラアルゴリズムの応用
ダイクストラ法は幅広い用途があります。中でも、ネットワーク分野で広く利用されています。以下に、ダイクストラ法の実際の使用例をいくつか紹介します。
ダイクストラは Google マップ： 上記のコードスニペットの出力からもわかるように、このアルゴリズムは最短経路を見つけるための基盤となるものです。
Google 単純なダイクストラアルゴリズムは使用しません。代わりに、改良版を使用します。目的地を選択すると、複数の経路が表示されます。 Google 地図。これらの経路のうち、いくつかはユーザー向けに整理されています。これらの経路は「時間」に基づいて選択されます。つまり、「時間」は最短経路のエッジコストとなります。
IPルーティングにおけるダイクストラ法： IPルーティング IPルーティングはネットワーク用語です。データパケットがさまざまな経路を経由して受信側に送信される方法を説明します。これらの経路は、ルーター、サーバー、その他の機器で構成されます。IPルーティングには、さまざまな種類のプロトコルがあります。
これらのプロトコルは、ルーターがデータを送信するための最短経路を見つけるのに役立ちます。プロトコルの1つに「OSPF（Open Shortest Path First）」があります。OSPFはダイクストラ法を使用します。ルーターは経路テーブルを保持し、各ルーターはそのテーブルを隣接ルーターと共有します。更新されたテーブルを受け取った後、ルーターはすべての経路を再度計算する必要があります。その際、ルーターはダイクストラ法を使用します。
ダイクストラアルゴリズムの限界
ダイクストラ法は、負のエッジを持つグラフにおいて最短経路を保証することはできません。ダイクストラ法は以下の原理に従います。
- あるノードから別のノードへは XNUMX つの最短パスが取られます。
- XNUMX つのノード間の最短パスが選択されると、再度計算されることはありません。
ここで、負のエッジを持つ XNUMX つの例に注目してください。
左のグラフでは、 頂点は3つあります。ダイクストラ法は、グラフ上で次のように実行されます。
ステップ1） 開始頂点「1」はゼロに初期化されます。 他のノードは無限大になります。
ステップ2） ノード「1」を訪問済みとしてマークし、最短経路に含める。
ステップ3） 最短経路がまだ計算されていないため、始点ノード1からノード「2」および「3」までの距離は無限大に設定されます。したがって、無限大よりもコストの低い経路はすべて最短経路に追加されます（貪欲法）。
ステップ4） ソース頂点「1」から「2」までの距離を更新します。現在の重みは5（5＜無限大）です。同様に、ノード「1」から「3」までの距離を重み3で更新します。
ステップ5） ここで、ノード「1」からの最短距離を調べてみると、エッジ1→2の最短距離は5であることがわかります。したがって、ノード「2」は訪問済みとしてマークされます。同様に、ノード「3」も最短距離が3であるため、訪問済みとしてマークされます。
しかし、よく見ると、コストがわずか2のパス1-3-2が存在します。ところが、ダイクストラ法では、ノード「1」からノード「2」までの最短距離は5と示されています。つまり、ダイクストラ法は最短距離を正しく計算できていません。その理由は、ダイクストラ法が貪欲アルゴリズムであるためです。そのため、一度訪問済みとマークされたノードは、より短いパスが存在する可能性があっても再検討されません。この問題は、エッジのコストが負の値、または重みが負の値の場合にのみ発生します。
ダイクストラ法は、このシナリオでは2つのノード間の最短経路を計算できません。そのため、このアルゴリズムにはいくつかの欠点があります。この負のエッジの問題を解決するために、「ベルマン・フォードアルゴリズム」と呼ばれる別のアルゴリズムが使用されます。このアルゴリズムは負のエッジにも対応できます。
ダイクストラのアルゴリズムの複雑さ
上記の実装では2つの「for」ループが使われています。これらのループは頂点の数だけ実行されます。したがって、時間計算量は O(V²)ここで、「O」という用語は、ダイクストラアルゴリズムの前提条件を示す表記法です。
グラフは「優先度キュー」を使用して格納できます。優先度キューはバイナリヒープデータ構造です。2D行列よりも効率的です。コストが最小のエッジは高い優先度を持ちます。すると、時間計算量は O(E log V)。 ここで、E はエッジの数、V は頂点の数です。
空間計算量は O(V²)、隣接行列を使用しているため(2D配列) 空間計算量は、隣接リストまたはキュー データ構造を使用して最適化できます。
