「幅優先探索はわかるけどダイクストラ法は怪しい」あなたに - Qiita

まえがき ふと幅優先探索と比べながらダイクストラ法を考えてみたらとてもしっくりきたので、記事に残したいなと思い、書いています。今までは、恥ずかしながらダイクストラ法はいまいち直感的にしっくりこず、知識として覚えて使っていました。 三角関数の公式を丸暗記せず、問題用紙の隅に単位円を書いて考えていたようなあなた (や、わたし) には、このように見方を変えてみるとひょっとしたら覚えやすいかもしれないです。 この記事で扱うこと 幅優先探索の復習をし、幅優先探索に「ある高速化テク」を適用しようとすると自然にダイクストラ法が導かれることを、なるべく直感的に説明します。 この記事で扱わないこと 「ダイクストラ法が必ず最短経路を見つける」こと、「ダイクストラ法が見つけた経路が必ず最短経路である」ことなどの厳密な説明はこの記事では扱いません。 前知識：幅優先探索とダイクストラ法の使い分け 大前提として、幅優