最短経路を求めるには
問題
- ダイクストラ
- ARC090 Avoiding Collision 解説
- JOI 象使い 問題 解説
- AOJ 認証レベル 解説 (ちょっと変えたダイクストラ)
- RUPC2018 Day2 Light 解説
- KOJ No.73 観光計画 解説(最大値ダイクストラ)
- AC 迷路 解説
- CF372 Complete The Graph
- AOJ Gridgedge 解説
- AOJ スギ (Demon's Cedar) 解説
- yukicoder No.788 トラックの移動 解説
- AOJ こたつがめを燃やさないで 解説
- yukicoder No.807 umg tours 解説
- [https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_g:title=
- ベルマンフォード
- BFS
発展的話題 KSP: k-th shortest path (裏取りできてない情報が含まれます)
コメントで指摘があったので、いったん取り下げた。
全く理解できてないですね…キーワードだけ残しておくことにした。
公開から5年くらい経って、ちょっと調べてみると日本語の記事も多く出ていたので、興味がある方は以下キーワードをもとにそちらを参照お願いします。
- 問題
- Yen's Algorithm
- ↑の問題の想定解法。解説は細かく書いてあるので、見て理解してもいい
計算量はO(KN(M+NlogN)), Kはk-thのk、Nは頂点数、Mは辺数ダイクストラの派生っぽい。たぶんlaycrsさんのツイートで言及している方法と同じだと思う
- Eppstein's Algorithm
↑の問題で使えるかわからないが、こういうのもある。k shortest path routing - Wikipediaを見ると、Yenはlooplessで使えて、Eppsteinはloopyでも使えるとあるので、Eppsteinの方が上位互換なのかな?(未検証)