一般的なダイクストラ法
概要
ダイクストラ法を使うと、単一始点 s から全ての頂点への最短距離が計算できるのは有名だね。これを少し拡張することで、「s からの最短距離と、それを実現する最短経路の個数」の組を、全ての頂点について計算することができるわ。
詳しく
少し天下り的だけど、以下の半環を考える。
(a, x) + (b, y) := a < b ? (a, x) : a > b ? (b, y) : (a, x + y),
(a, x) * (b, y) := (a + b, x * y)
この半環を使って、[Mohri2002]の方法でダイクストラ法を行うことにより、s-vの最短距離とs-vの最短経路の個数が全ての頂点vについて分かる。
ソースコードは以下の通り。
ARC090 E - Avoiding Collision で確かめた。
https://beta.atcoder.jp/contests/arc090/submissions/2036319
参考文献
[Mohri2002] Mohri, Mehryar. "Semiring frameworks and algorithms for shortest-distance problems." Journal of Automata, Languages and Combinatorics 7.3 (2002): 321-350.
