@mine19876293 (ミッキー)

Are you sure you want to delete the question?

If your question is resolved, you may close it.

Leaving a resolved question undeleted may help others!

We hope you find it useful!

ダイクストラ

解決したいこと

ダイクストラの正しいルートがわからないので、
質問させていただきます。

⓵:v1→v2→v4と行ってダイクストラ法だと、未確定の
数字を次に選択するので、v4からだと、v3に行く数字の方が
少ない距離なので、v3を選択するのが自分は正しいと自分は思ってるのですが、解答はv5を選択してます。わかりやすく、解説していただけたら、ありがたいです。

⓶:⓵と同様、v1→v3→と行って未確定の
数字を次に選択するので、v3からだと、v4に行く数字の方が
少ない距離なので、「v4を選択するのが自分は正しいと自分は思ってるのですが、解答はv5を選択してます。なぜでしょうか?

図)
令和6年春期_午後問3_図1.png

解答)

【1回目】

最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV1<0>なので、V1までの最短距離が0で確定する。V1を更新起点ノードとして、隣接するV2、V3の始点距離ノードを計算すると、V1→V2が10、V1→V3が16なので、V2<10>、V3<16>のままとなる(更新なし)。

---

【2回目】

最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV2<10>なので、V2までの最短距離が10で確定する。V2を更新起点ノードとして、隣接するV3、V4の始点距離ノードを計算すると、V2→V3が14、V2→V4が13なので、V3<14>、V4は<13>で更新される。

---

【3回目】

最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV4<13>なので、V4までの最短距離が13で確定する。V4を更新起点ノードとして、隣接するV3、V5の始点距離ノードを計算すると、V4→V3が15、V4→V5が19なので、V5は<19>で更新される。

---

【4回目】

最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV3<14>なので、V3までの最短距離が14で確定する。V3を更新起点ノードとして、隣接するV5の始点距離ノードを計算すると、V3→V5が17なので、V5は<17>で更新される。

---

【5回目】

最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV5<17>なので、V5までの最短距離が17で確定する。V5は終点なので処理が終了する。
0 likes

4Answer

「少ない距離」が「そのノードと次のノードの距離」というより、「スタートからの距離が少ない方」ということだと思います。

↓ こちらが分かりやすいかも

1Like

専門ではないですが、グラフ理論が専門なんて少ないでしょうしコメントさせていただきます。

①について。
質問では
「解答はv5を選択してます」とおっしゃっているのですが、そもそも解答の中に選択なんて言葉は出てきていません。
3回目においてV3を更新していない理由としては、既に14で更新されており、ここで計算した15が最短ではないからです。

②について。
4回目の際にV4を更新しないのは、3回目の手順でV4が最短と既に確定しているからです。

別にあなたの考えが間違っている訳ではありませんが、上記回答が理由になっています。

ちなみに、既にコメントがある「ノード間の距離とスタートからの距離」というのはトートロジーです。混乱する場合は気にしないでOKかと思います。

0Like

①:v1→v2→v4と行ってダイクストラ法だと、未確定の
数字を次に選択するので、v4からだと、v3に行く数字の方が
少ない距離なので、v3を選択するのが自分は正しいと自分は思ってるのですが、解答はv5を選択してます。

「行く」とか「選択する」という言葉が
「解答)」内の記述における「更新起点ノードとして」を示すのであれば……

「解答)」は(あなたの考えの通りに)V4の次には「V3を選択」するという内容になっていると見えますよ.
(:【4回目】で V5 ではなくて V3 の側を「更新起点ノードとして…」とされています)

上記の通り,「解答)」は
V1 → V2 → V4 → V3 → V5
という順で探索が進んでいく(:最短距離が確定していく)ことを示しています.

V3 の次に再度 V4 に行かない理由は,その時点では V4 は「最短距離が確定していないノード」に含まれていないからです.
(: V1 → V2 → V4 → V3 まできた時点で「最短距離が確定していないノード」として残っているのは V5 だけです)

0Like

ダイクストラ法がよく分かってないようですので、例題を解答に沿って解いてみましょう。

まず、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について距離を計算する必要はありません。

0Like

Your answer might help someone💌