Dijkstraのアルゴリズムは、コンピュータサイエンスで使用される一般的な方法です。これは、ノード間の最も短いパスをグラフで見つけることができます。ネットワークルーティング、マップナビゲーション、およびさまざまな最適化の問題で広く適用されます。この記事では、Digikstraのアルゴリズムを使用して計算を実行する手順の概要を説明します。

アルゴリズムの理解

アルゴリズムは、最小の暫定距離でノードを選択することで、その隣接するノードへの距離を更新します。 ターゲットノードへの最短パスが発見されるか、すべてのノードが処理されるまで続きます。

工程ごとの計算プロセス

ノードA、B、C、D、E、および次の重みのあるエッジを持つグラフを仮定します。

  • A から B: 4
  • A から C: 2
  • BからCまで: 1
  • BからD: 5
  • C から D: 8
  • CからE: 10
  • D から E: 2

ノードAから始まって、距離を初期化します。A = 0、その他 = 無限。 ノードを全て非指示としてマークします。

反復 1

ノード A (distance 0) を選択します。 隣接するノード B と C を更新します。

B: 4 (A + 4) への距離、C: 2 (A + 2)。 訪問したように A マーク。

反復 2

ノードC(distance 2)を選択します。 隣接するDとEを更新します。

D: 10 (C + 8) への距離、E: 12 (C + 10)。 マーク C を訪問しました。

反復 3

ノードB(距離4)を選択します。 隣接するDを更新します。

D: 9 (B + 5) への距離は、以前の 10. に更新します。 D の間隔は 9. マーク B 訪問したように。

反復 4

ノードD(distance 9)を選択します。 隣接するEを更新します。

E: 11 (D + 2) への間隔。訪問されるように E の間隔を 11. にマーク D 更新して下さい。

反復 5

ノードEは訪問した11. Mark Eの距離を持っています。 AからEまでの最短パスは、C、B、D、Eを全距離で通過します。11