色の知識で人生の可能性が広がる!みんなに役立つ色彩検定 >>

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

教えて!goo グレード

A 回答 (2件)

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



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

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

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

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

    • good
    • 0
この回答へのお礼

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

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

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

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

教えて!goo グレード

このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング