Dijsktra のアルゴリズム: C++、Python コード例

最短経路または最短距離は何ですか?

コストが最小となるソース頂点から宛先頂点までのパスが、最短パスまたは最短距離です。 グラフ理論では、送信元から宛先までのルートが複数存在する可能性があります。 これらの経路の間に、コストが最小となる経路があれば、それを最短経路アルゴリズムと呼ぶことができます。

ここで、「コスト」とは、ルート内のノードの数、または各パスのコストの合計を意味します。 パスには XNUMX つまたは複数のエッジを含めることができます。 XNUMX つの頂点間の接続を「エッジ」と呼びます。 最短経路アルゴリズムには、ダイクストラアルゴリズム、ベルマンフォードアルゴリズムなど、さまざまな種類があります。

ここではダイクストラのアルゴリズムについて説明します。

続きを見てみましょうwing 重み付けされたグラフ:

無向重み付きグラフ
無向重み付きグラフ
  • 「加重」という用語は、あるノードから別のノードにコストを移動することを意味します。 たとえば、ノード 1 からノード 2 に移動すると、コストまたは重みは 1 になります。
  • ノード 1 とノード 2 の間のパスはエッジと呼ばれます。
  • 「無指向」とは、あるノードを別のノードに移動したり、前のノードに戻ったりできることを意味します。 したがって、ノード 1 からノード 7 までのすべてのルートを検索しようとすると、次のようになります。
ルートまたはパス 費用
1-2-6 (1+3+3) = 7
1-2-3 (1+9+1) = 11
1-3-7 (7 + 1)= 8
1-4-5 (6+2+5) = 13

これら 7 つのルートのうち、最初のルートのコストは XNUMX であることがわかります。つまり、コストの点で最も短いルートです。

最短経路

最短経路

ダイクストラのアルゴリズムの仕組み

ダイクストラ アルゴリズムは、有向および無向の両方の重み付きグラフで最短距離を見つけることができます。 このアルゴリズムは常に原点から最短または最も近いノードを選択するため、貪欲です。 「貪欲」という用語は、一連の結果または結果の中から、アルゴリズムがそれらの中で最良のものを選択することを意味します。

ここでは、他のすべてのルートの中から最短のパスを見つけようとしています。 したがって、ダイクストラのアルゴリズムは、単一の宛先ノードからの最短パスをすべて見つけます。 その結果、次のように動作します。 貪欲なアルゴリズム.

以下の「例」セクションでは、段階的なアプローチを示します。 次のように動作します。

ステップ1) 開始ノードをコスト 0 で初期化し、ノードの残りの部分を無限コストとして初期化します。
ステップ2) 訪問したノードを追跡するために配列またはリストを維持します
ステップ3) ノードコストを最小コストで更新します。 これは、現在のコストとパス コストを比較することで実行できます。 (デモは例のセクションに示されています)
ステップ4) すべてのノードにアクセスするまでステップ 3 を続けます。

これらの手順をすべて完了すると、送信元から宛先までのコストが最小となるパスが見つかります。

ダイクストラとBFS、DFSの違い

ダイクストラと BFS-DFS の主な違いは、ダイクストラが最短経路探索アルゴリズムであり、BFS、DFS が経路探索アルゴリズムであることです。 一般に、BFS と DFS はパスを検索する際にコストを考慮しません。 したがって、これらのアルゴリズムは最短パスを保証できません。

BFS がどのように機能するかを示す 2D グリッドのデモンストレーション

2D グリッドのデモンストレーション

アルゴスケッチ、しょうwing BFS のデモンストレーション

このデモは、BFS がパスを検索するだけであることを示しています。 ただし、パスの重みは気にされません。 BFS (幅優先探索) は、あるノードから別のノードへの移動にかかるコストが 1 だけであると想定しています。

しかし、グラフの例を見てみましょう。

2D グリッドのデモンストレーション

ここでは、レベル 2 でパスを見つけます。BFS はレベル順にグラフを走査します。 したがって、次のように移動します。

ステップ1) ノード「1」から開始して、隣接するすべてのノード 2,3,4、XNUMX、XNUMX を訪問します。

ステップ2) ノード 2,3,4、1、XNUMX をレベル XNUMX としてマークし、それらの隣接ノードにアクセスします。 目的のノードに到達するまで、隣接するすべてのノードの探索を続けます。

DFS に関しては、次のように 1 から 7 までのパスをたどります。wing:

  • 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 は次のことを行いますwing:

  • 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 ルーティングにはさまざまな種類のプロトコルがあります。

これらのプロトコルは、ルーターがデータを送信するための最短パスを見つけるのに役立ちます。 プロトコル名の一つに「OSPF(Open Shortest Path First)」というものがあります。 OSPF はダイクストラ アルゴリズムを使用します。 ルーターはルートのテーブルを維持します。 各ルータはares 近隣ルーターとのテーブル。 更新されたテーブルを受信した後、すべてのパスを再度計算する必要があります。 このとき、ルーターはダイクストラ アルゴリズムを使用します。

ダイクストラアルゴリズムの限界

ダイクストラ アルゴリズムは、ネガティブ エッジ グラフ内の最短パスを保証できません。 ダイクストラ アルゴリズムは次の方法論に従います。

  • あるノードから別のノードへは XNUMX つの最短パスが取られます。
  • XNUMX つのノード間の最短パスが選択されると、再度計算されることはありません。

ここで、負のエッジを持つ XNUMX つの例に注目してください。

ダイクストラアルゴリズムの限界

左側のグラフでは、 頂点がXNUMXつあります。 ダイクストラは次のようにグラフ上で実行されます。wing:

ステップ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 つのノード間の最短パスの計算に失敗します。 結果として、このアルゴリズムにはいくつかの欠点があります。 このネガティブエッジの問題を解決するために、「ベルマン・フォードアルゴリズム」と呼ばれる別のアルゴリズムが使用されます。 このアルゴリズムは負のエッジでも機能します。

ダイクストラのアルゴリズム コムplexITY

上記の実装では XNUMX つの「for」ループを使用しました。 これらのループは頂点の数だけ実行されます。 それで、タイムコムplex性は O(V2)。 ここで、「0」という用語は、ダイクストラアルゴリズムの仮定を与える表記を意味します。

「Priority Queue」を使用してグラフを保存できます。 プライオリティ キューはバイナリ ヒープ データ構造です。 2D マトリックスよりも効率的です。 最小コストのエッジの優先度が高くなります。

それからタイムコムplexなるだろう O(E log(V))。 ここで、E はエッジの数、V は頂点の数です。

スペースコムplex性は O(V2)、隣接行列を使用しているため(2D配列)。 スペースコムplex隣接リストまたはキュー データ構造を使用して最適化できます。