ダイシュクトラのアルゴリズム: C++, Python コードの例
サラ・チェン
最短経路または最短距離は何ですか?
コストが最小となるソース頂点から宛先頂点までのパスが、最短パスまたは最短距離です。 グラフ理論では、送信元から宛先までのルートが複数存在する可能性があります。 これらの経路の間に、コストが最小となる経路があれば、それを最短経路アルゴリズムと呼ぶことができます。
ここで「コスト」とは、経路上のノードの数、または各経路のコスト合計を意味します。経路には 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 |
これら 7 つのルートのうち、最初のルートのコストは XNUMX であることがわかります。つまり、コストの点で最も短いルートです。
ダイクストラのアルゴリズムの仕組み
ダイクストラ アルゴリズムは、有向および無向の両方の重み付きグラフで最短距離を見つけることができます。 このアルゴリズムは常に原点から最短または最も近いノードを選択するため、貪欲です。 「貪欲」という用語は、一連の結果または結果の中から、アルゴリズムがそれらの中で最良のものを選択することを意味します。
ここでは、他のすべてのルートの中から最短のパスを見つけようとしています。 したがって、ダイクストラのアルゴリズムは、単一の宛先ノードからの最短パスをすべて見つけます。 その結果、次のように動作します。 貪欲なアルゴリズム.
以下の「例」セクションでは、段階的なアプローチを示します。 次のように動作します。
ステップ1） 開始ノードをコスト 0 で初期化し、ノードの残りの部分を無限コストとして初期化します。
ステップ2） 訪問したノードを追跡するために配列またはリストを維持します
ステップ3） ノードコストを最小コストで更新します。 これは、現在のコストとパス コストを比較することで実行できます。 (デモは例のセクションに示されています)
ステップ4） すべてのノードにアクセスするまでステップ 3 を続けます。
これらの手順をすべて完了すると、送信元から宛先までのコストが最小となるパスが見つかります。
ダイクストラとBFS、DFSの違い
Dijkstra と BFS-DFS の主な違いは、Dijkstra が最短経路探索アルゴリズムであるのに対し、BFS、DFS は経路探索アルゴリズムである点です。一般的に、BFS と DFS は経路探索中にコストを考慮しません。そのため、これらのアルゴリズムは最短経路を保証することはできません。
BFS がどのように機能するかを示す 2D グリッドのデモンストレーション
このデモは、BFS がパスを検索するだけであることを示しています。 ただし、パスの重みは気にされません。 BFS (幅優先探索) は、あるノードから別のノードへの移動にかかるコストが 1 だけであると想定しています。
しかし、グラフの例を見てみましょう。
ここでは、レベル 2 でパスを見つけます。BFS はレベル順にグラフを走査します。 したがって、次のように移動します。
ステップ1） ノード「1」から開始して、隣接するすべてのノード 2,3,4、XNUMX、XNUMX を訪問します。
ステップ2） ノード 2,3,4、1、XNUMX をレベル XNUMX としてマークし、それらの隣接ノードにアクセスします。 目的のノードに到達するまで、隣接するすべてのノードの探索を続けます。
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、XNUMX はノード XNUMX の隣接ノードです。
コストを更新するときは、次の手順に従う必要があります。
上記の式を使用して各ノードのコストを更新できます。 たとえば、ノード 1 にいて、その隣接ノード 2,3,4、XNUMX、XNUMX のコストを更新する必要がありました。
アップデート後のコストまたは重量は次のようになります。
ステップ 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、XNUMX の後は、次のようになります。
現在、パス 1-3-7 のコストは 8 (以前) です。 ノード「7」からノード「7」に到達できるため、ノード「6」は訪問済みとしてマークされませんでした。 パス「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 になります。
疑似コード ダイクストラのアルゴリズム
ダイクストラアルゴリズムの疑似コードは次のとおりです。
Dijkstra(G, S):
for each vertex V in G
distance[V] & lt; - Infinity
previous[V] & lt; - NULL
if V does not equal S, then,
(priority queue) Q.push(V)
distance[S] = 0
While Q is not empty
U & lt; - Extract the MIN from Q
For each unvisited adjacent V of U
TotalDistance & lt; - distance[U] + edge_cost(U, V)
if TotalDistance is less than distance[V], then
distance[V] & lt; - TotalDistance
previous[V] & lt; - 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] & amp; & 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] & amp; & graph[U][j] & amp; &
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 ダイクストラアルゴリズムの実装
ダイクストラのアルゴリズムを実装するには、 パイソン、コードは次のとおりです。
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] & lt; = _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 & lt;
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 ルーティングにはさまざまな種類のプロトコルがあります。
これらのプロトコルは、ルータがデータを送信するための最短パスを見つけるのに役立ちます。プロトコル名の 1 つは「OSPF (Open Shortest Path First)」です。OSPF はダイクストラ アルゴリズムを使用します。ルータはルートのテーブルを維持します。各ルータはテーブルを近隣ルータと共有します。更新されたテーブルを受信した後、ルータはすべてのパスを再度計算する必要があります。その際、ルータはダイクストラ アルゴリズムを使用します。
ダイクストラアルゴリズムの限界
ダイクストラ アルゴリズムは、ネガティブ エッジ グラフ内の最短パスを保証できません。 ダイクストラ アルゴリズムは次の方法論に従います。
- あるノードから別のノードへは XNUMX つの最短パスが取られます。
- XNUMX つのノード間の最短パスが選択されると、再度計算されることはありません。
ここで、負のエッジを持つ XNUMX つの例に注目してください。
左側のグラフでは、 頂点は 3 つあります。ダイクストラ法は次のようにグラフ上で実行されます。
ステップ1） 開始頂点「1」はゼロに初期化されます。 他のノードは無限大になります。
ステップ2） ノード「1」を訪問済みとしてマークし、最短パスに含めます。
ステップ3） 最短パスはまだ計算されていないため、ソース ノード 1 からノード "2" および "3" までの距離は無限大に設定されます。 したがって、コストが無限大未満のパスはすべて最短パスに追加されます (貪欲なアプローチ)。
ステップ4） ソース頂点またはソースノードからの距離「1」を「2」に更新します。 現在の重みは 5 になります (5
ステップ5） ここで、ノード「1」からの最短距離を確認すると、エッジ 5->1 の最短距離は 2 であることがわかります。したがって、ノード「2」は訪問済みとしてマークされます。
同様に、ノード「3」も最短距離が 3 であるため、訪問済みとしてマークされます。
しかし、観察すると、コストがわずか 1 のパス 3-2-2 が存在します。しかし、ダイクストラは、ノード「1」からノード「2」までの最短距離は 5 であることを示しています。したがって、ダイクストラは最短距離を計算できませんでした。正しく距離を置きます。 このようなことが起こった理由は、ダイクストラが貪欲なアルゴリズムであるためです。 したがって、ノードが訪問済みとしてマークされると、利用可能なより短いパスがある可能性があっても、再検討されることはありません。 この問題は、エッジに負のコストまたは負のウェイト エッジがある場合にのみ発生します。
このシナリオでは、ダイクストラは XNUMX つのノード間の最短パスの計算に失敗します。 結果として、このアルゴリズムにはいくつかの欠点があります。 このネガティブエッジの問題を解決するために、「ベルマン・フォードアルゴリズム」と呼ばれる別のアルゴリズムが使用されます。 このアルゴリズムは負のエッジでも機能します。
ダイクストラのアルゴリズムの複雑さ
上記の実装では2つの「for」ループが使われています。これらのループは頂点の数だけ実行されます。したがって、時間計算量は O(V2)。 ここで、「0」という用語は、ダイクストラアルゴリズムの仮定を与える表記を意味します。
「Priority Queue」を使用してグラフを保存できます。 プライオリティ キューはバイナリ ヒープ データ構造です。 2D マトリックスよりも効率的です。 最小コストのエッジの優先度が高くなります。
すると、時間計算量は O（E log（V））。 ここで、E はエッジの数、V は頂点の数です。
空間計算量は O(V2)、隣接行列を使用しているため(2D配列) 空間計算量は、隣接リストまたはキュー データ構造を使用して最適化できます。
