これはCompetitive Programming Advent Calendar 2015 の19日目の記事です。 さて、表題の通りこの記事はダイクストラ法についての思い出を語るものです。 競プロライフも2周年を迎え、取り組み始めたころに比べればかなりいろいろな問題も解けるようになりますます楽しくなってきたのですが、最初の頃割と長い間しっくりこないというか苦手意識のあったダイクストラ法について、振り返りながらいろいろ書いてみようと思います。 対象としてはダイクストラが分からなくてググるくらいの人も想定しています。ので多少くどい感じですがご容赦のほど。あともし大きな間違い等あればお知らせください。 ダイクストラ法とは ダイクストラ法 - Wikipedia いきなりwikipediaを貼ってしまいましたが、グラフにおいてある頂点から別の頂点への最短距離を求める問題(単一始点最短経路問題)
![ダイクストラ法が分からなかった君のために - kuuso1のブログ](https://cdn-ak-scissors.b.st-hatena.com/image/square/65867e729a880a8856071fd6c62fb5894403a12a/height=288;version=1;width=512/http%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fk%2Fkuuso1%2F20151213%2F20151213071247.png)