読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

ダイクストラ法とその例題

ダイクストラ法とその例題についてまとめておきます。

例題はワーシャルフロイドのやつ使いまわしです(ダイクストラ向きのは二分探索とか絡んで難しいので……)

ダイクストラ法とは?

ダイクストラ法(Dijkstra's algorithm)は、グラフのある点から各点までの最短経路を求めるアルゴリズム

内容については以下が詳しい。

ざっくりまとめると以下の通り。

  • 計算量が O(V^2)で済む*1 (ワーシャルフロイドは O(V^3))
  • 負の長さが存在するときは適用できない(そのときはベルマンフォード法を使う)
  • 始点が固定なので、始点も終点もばらばらな最短経路をたくさん求めたいときはワーシャルフロイドで一気にやった方がラク

例題

せっかくダイクストラを学んだからには「ダイクストラだからこそ!」という問題を解きたいものですが、典型アルゴリズムなだけあって捻った出題をされることが多いようです。そのためダイクストラの肩慣らし的な問題がなかなか見つかりませんでした(´・ω・`)

ということで、こちらの記事で紹介した、ワーシャルフロイドで解ける問題をダイクストラ法でも解いてみましょう(まだワーシャルフロイドやってない!という人はどっちから始めても大丈夫です)

注意点として、ダイクストラ法では始点を変えるたびにvisited, costなどの配列を初期化しなければならないことに気をつけましょう!(自分はここでだいぶはまった)

参考

ワーシャルフロイドでの解答例は以下の記事にあります。

pakapa104.hatenablog.com

*1:プライオリティーキューを使えばさらに (E+V)\log Vまで落とせるらしいですがまだそこまではやってません><