ダイクストラ法がよく分かってないようですので、例題を解答に沿って解いてみましょう。
まず、V1~5の5ノードでV1が始点ですので、初期状態は下記のようになっています。
最短距離未確定ノード |
最短距離確定ノード |
V1<0>, V2<10> V3<16>, V4<->, V5<-> |
|
解答の1回目の操作を行いましょう。
【1回目】
最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV1<0>なので、
V1までの最短距離が0で確定する。
V1を更新起点ノードとして、隣接するV2、V3の始点距離ノードを計算すると、
V1→V2が10、V1→V3が16なので、V2<10>、V3<16>のままとなる(更新なし)。
まず、最短距離未確定ノードのうちV1<0>が最小距離なので、確定ノードの方に移動し、更新起点ノードとして選択します。
そして、V1に隣接するノードのうち最短距離が未確定のノードを探します。
確定済みノードは隣接していませんので、V2<10>とV3<16>ですね。
まずV2<10>について計算します。
V1の始点ノード距離が0でV1->V2の距離が10なので、V1->V2を通る始点ノード距離は$0+10=10$で、現状の距離(V2<10>)と一緒なので更新なしです。
次にV3<16>について計算します。
V1の始点ノード距離が0でV1->V3の距離が16なので、V1->V3を通る始点ノード距離は$0+16=16$で、現状の距離(V3<16>)と一緒なので更新なしです。
結果、下記のようになります。
最短距離未確定ノード |
最短距離確定ノード |
V2<10>, V3<16>, V4<->, V5<-> |
V1<0> |
解答の2回目の操作を行いましょう。
【2回目】
最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV2<10>なので、
V2までの最短距離が10で確定する。
V2を更新起点ノードとして、隣接するV3、V4の始点距離ノードを計算すると、
V2→V3が14、V2→V4が13なので、V3<14>、V4は<13>で更新される。
まず、最短距離未確定ノードのうちV2<10>が最小距離なので、確定ノードの方に移動し、更新起点ノードとして選択します。
そして、V2に隣接するノードのうち最短距離が未確定のノードを探します。
V1<0>はすでに確定ずみですので、V3<16>とV4<->ですね。
まずV3<16>について計算します。
V2の始点ノード距離が10でV2->V3の距離が4なので、V2->V3を通る始点ノード距離は$10+4=14$で、現状の距離(V3<16>)より小さいのでV3<14>に更新します。
次にV4<->について計算します。
V2の始点ノード距離が10でV2->V4の距離が3なので、V2->V4を通る始点ノード距離は$10+3=13$で、現状の距離(V4<->)はありませんのでV4<13>に更新します。
結果、下記のようになります。
最短距離未確定ノード |
最短距離確定ノード |
V3<14>, V4<13>, V5<-> |
V1<0>,V2<10> |
解答の3回目の操作を行いましょう。
【3回目】
最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV4<13>なので、
V4までの最短距離が13で確定する。
V4を更新起点ノードとして、隣接するV3、V5の始点距離ノードを計算すると、
V4→V3が15、V4→V5が19なので、V5は<19>で更新される。
まず、最短距離未確定ノードのうちV4<13>が最小距離なので、確定ノードの方に移動し、更新起点ノードとして選択します。
そして、V4に隣接するノードのうち最短距離が未確定のノードを探します。
V2<10>はすでに確定ずみですので、V3<14>とV5<->ですね。
まずV3<14>について計算します。
V4の始点ノード距離が13でV4->V3の距離が2なので、V4->V3を通る始点ノード距離は$13+2=15$で、現状の距離(V3<14>)より大きいので更新しません。
次にV5<->について計算します。
V4の始点ノード距離が13でV4->V5の距離が6なので、V4->V5を通る始点ノード距離は$13+6=19$で、現状の距離(V5<->)はありませんのでV5<19>に更新します。
結果、下記のようになります。
最短距離未確定ノード |
最短距離確定ノード |
V3<14>, V5<19> |
V1<0>,V2<10>,V4<13> |
解答の4回目の操作を行いましょう。
【4回目】
最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV3<14>なので、
V3までの最短距離が14で確定する。
V3を更新起点ノードとして、隣接するV5の始点距離ノードを計算すると、
V3→V5が17なので、V5は<17>で更新される。
まず、最短距離未確定ノードのうちV3<14>が最小距離なので、確定ノードの方に移動し、更新起点ノードとして選択します。
そして、V3に隣接するノードのうち最短距離が未確定のノードを探します。
V1<0>,V2<10>,V4<13>はすでに確定ずみですので、V5<19>ですね。
V5<19>について計算します。
V3の始点ノード距離が14でV3->V5の距離が3なので、V4->V5を通る始点ノード距離は$14+3=17$で、現状の距離(V5<19>)より小さいのでV5<17>に更新します。
結果、下記のようになります。
最短距離未確定ノード |
最短距離確定ノード |
V5<17> |
V1<0>,V2<10>,V3<14>,V4<13> |
解答の5回目の操作を行いましょう。
【5回目】
最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV5<17>なので、
V5までの最短距離が17で確定する。
V5は終点なので処理が終了する。
まず、最短距離未確定ノードのうちV5<17>が最小距離なので、確定ノードの方に移動し、更新起点ノードとして選択します。
V5は終点ノードなので、操作を終了します。
結果、下記のようになります。
最短距離未確定ノード |
最短距離確定ノード |
|
V1<0>,V2<10>,V3<14>,V4<13>,V5<17> |
上記の手順について、ちゃんと一つ一つ確認してもらえれば質問についてはどちらも見当違いなことを言っているとご理解いただけるかと思いますが、一応解答しておきます。
質問1のV4の次にV3ではなくV5を選択している、というのはおそらく3回目の下記の部分かと思います。
V4を更新起点ノードとして、隣接するV3、V5の始点距離ノードを計算すると、V4→V3が15、V4→V5が19なので、V5は<19>で更新される。
上の手順を確認してもらえればわかると思いますが、V3を更新せずV5を更新したのは、V3は距離が縮まらなかったので更新せず、V5は距離が縮まったから更新した、というだけです。
質問2については、V3を更新起点ノードにした時点で、V4は距離13で確定しているので、V4について距離を計算する必要はありません。