グラフを通る最短経路を計算するダイクストラのアルゴリズム

例

アルゴリズムの動作は、例を使用して最もよく理解できます。次のように重み付きエッジで接続された、AからGまでのノードがマークされた次のグラフについて考えてみます-

初期化は次のようになります-

• dist [7] ={0、∞、∞、∞、∞、∞、∞}

• Q ={A、B、C、D、E、F、G}

• S𝑆=∅

パス1 −ノード Aを選択します Qから dist []が最も低いため 0の値 Aの隣接ノードはBとCです。アルゴリズムに従ってBとCに対応するdist[]値を更新します。したがって、データ構造の値は次のようになります-

• dist [7] ={0,5,6、∞、∞、∞、∞}

• Q ={B、C、D、E、F、G}

• S ={A}

このパスの後の距離と最短経路を次のグラフに示します。緑のノードは、S-

パス2 −ノード Bを選択します Qから dist []が最も低いため 5の値 Sに入れます。 Bの隣接ノードはC、D およびE 。 C、Dに対応するdist[]値を更新します アルゴリズムによるとE。したがって、データ構造の値は次のようになります-

• dist [7] ={0,5,6,12,13、∞、∞}

• Q ={C、D、E、F、G}

• S ={A、B}

このパスの後の距離と最短経路は-

パス3 −ノード Cを選択します Qから 最小のdist[]値が6であり、Sに配置されているためです。Cの隣接ノードはDとFです。DとFに対応するdist []値を更新します。したがって、データ構造の値は-

• dist [7] ={0,5,6,8,13,10、∞}

• Q ={D、E、F、G}

• S ={A、B、C}

このパスの後の距離と最短経路は-

パス4 −ノード Dを選択します Qから 距離[が最も低いため ] 値を8にして、Sに入れます。Dの隣接ノードはE、F、Gです。 dist []を更新します。 E、Fに対応する値 およびG 。したがって、データ構造の値は次のようになります-

• dist [7] ={0,5,6,8,10,10,18}

• Q ={E、F、G}

• S ={A、B、C、D}

このパスの後の距離と最短経路は-

パス5 −ノードEまたはノード Fのいずれかを選択できます Qから どちらもdist[]が最も低いため 10の値 。 E など、いずれか1つを選択します 、 Sに入れます 。 Dの隣接ノード Gです 。 dist []を更新します Gに対応する値。したがって、データ構造の値は-

• dist [7] ={0,5,6,8,10,10,13}

• Q ={F、G}

• S ={A、B、C、D、E}

このパスの後の距離と最短経路は-

パス6 −ノード Fを選択します Qから dist []が最も低いため 10の値 Sに入れます 。 Fの隣接ノード Gです 。 dist [] Gに対応する値は、 Fを介した値よりも小さくなります 。だからそれは同じままです。データ構造の値は-

• dist [7] ={0,5,6,8,10,10,13}

• Q ={G}

• S ={A、B、C、D、E、F}

このパスの後の距離と最短経路は-

パス7 − Qにはノードが1つだけあります 。 Qから削除します Sに入れます。dist[]配列を変更する必要はありません。さて、 Q 空になります、 S すべてのノードが含まれているため、アルゴリズムは終了です。どのルートのパスにも含まれていないすべてのエッジまたはルートを削除します。したがって、ソースノードAから他のすべてのノードへの最短パスツリーは次のようになります-