ダイクストラ法の証明を教えてください。特に、最短路確定済みの点に隣接する点で、暫定の距離が最短のもの

ダイクストラ法の証明を教えてください。特に、最短路確定済みの点に隣接する点で、暫定の距離が最短のものが最短経路として確定になるのはなぜですか？

No.2 回答者： Tacosan 回答日時： 2022/08/10 01:21

「最短路確定済みの点に隣接する点で、暫定の距離が最短のもの」の「もの」は「点」だから, それが「最短経路として確定」ってのは日本語としておかしいんだが....

まあさておき, 「最短路確定済みの点に隣接する点」というのはまだ「最短路が確定していない」点だよね. で, そのうち「暫定の距離が最短のもの」に対して「最短経路」を確定させる, というのが Dijkstra法.

これに疑問を持つとしたらおそらく
別の経路でもっと短くなるんじゃないか
というところだと思うんだけど, 「全ての辺の長さが正」という条件でそんなことってある? 少なくとも, 「最短路が確定していない点」を経由すると, もっと長くなっちゃう (というか「短く」はならない) よね.

なお他の疑問があるなら「どのような疑問なのか」を具体的に書いてほしい.

No.1 回答者： Tacosan 回答日時： 2022/08/09 05:19

いちおうかくにんだがあなたのいう「ダイクストラ法」ってどういう方法でどういうものに適用できる?

この回答へのお礼

ありがとうございます。
最短路問題で辺の長さ全部正のときに使える認識です。

各段階の最短路確定のときに、「ホントに確定していいの？」が疑問になっています。

詳細
https://ja.m.wikipedia.org/wiki/%E3%83%80%E3%82% …

お礼日時：2022/08/09 15:49