[問題案] K-Shortest Paths (Undirected)

[NachiaVivias]

Problem name: K-Shortest Paths (Undirected) Problem ID: k_shortest_paths_undirected

問題

N 頂点 M 辺の無向グラフがあり、辺に正の長さがついている。 s,t 間の単純パスを、短い順に K 個計算してください。

計算量

• 雑に見積もって $O(K(N+M) \log (NMK))$
• $N,M \leq 1000$ , $K\leq 500$ とかかな

Reference

• [1] https://frosted-english-119.notion.site/Undirected-K-Shortest-Paths-86a6c9a076d942c9b6e1058859ccf566
• [2] https://noshi91.hatenablog.com/entry/2024/10/14/164225

入出力

• ref. K-Shortest Walk

k 行目には k 番目の最短パスの重みを出力、なければ -1 を出力。

Note / Disucussion

重み 0 の辺がある場合は重み eps で置き換えればよい [2] ので、正重みだけ verify できればよいと思います。

[maspypy]

https://github.com/yosupo06/library-checker-problems/issues/508 これと重複ですか？

[NachiaVivias]

そちらでは検討に入っていないように見えます。しかし仮に重複だとして、有向グラフの問題とは事情が結構違いそう(特に、有向は yukicoder に出題がある)なので分けると都合が良いと思います。

[maspypy]

ああ、あっちは有向でこっちは無向でした。理解。