最短経路を求めるには
問題
- ダイクストラ
- 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
- 問題
- 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の方が上位互換なのかな?(未検証)