[問題案] k shortest path

[null0124]

初 open issue です 問題ID: k_shortest_simple_path 問題名: K Shortest Simple Path

想定アルゴリズム: Yen's Algorithm 参考資料: https://yukicoder.me/problems/no/1069

問題概要

N 頂点 M 辺重み付き有向グラフが与えられるので、s -> t の path のコストを小さい順に k 個出力。存在しない場合は -1 を出力

入力

N M s t K
(グラフ)

出力

cost_1
...
cost_k

制約

N <= 10^3 1 <= M <= 10^3 0 <= c <= 10^9 k <= 10

[yosupo06]

ありがとうございます！

• M の制約はO(N)ですか？(元の問題から考えるに)
• 無向 or 有向？(雑に検索したら無向だともっと速いアルゴリズムがあると出てきたんですが、詳細を把握していません)
• パスは同じ頂点を通れない or 通れる？(これの通れないそう)

あたりをとりあえず教えてくれると助かります

[null0124]

コメントありがとうございます！

1, 単純グラフで大丈夫だと思うので、そうです 2, 無向で早くなる話初耳なんですが(調べます)、有向でいいかなという気持ちです。特にこだわりは無いです 早いアルゴリズムは https://qiita.com/hotman78/items/42534a01c4bd05ed5e1e などがあるらしいのですが、こちらで simple path は難しいっぽいです 3, simple path です

追加で、重みは 0 以上です

[yosupo06]

不明瞭な質問申し訳ないです、1で聞きたかったのは、辺数が1000か100,000かということでした(多分1000ですよね？)

この問題だと自己ループはないにしても多重辺は入れたい感じがします。

[null0124]

コメント送ったあとに意図に気づきました() 想定 N - 1 <= M <= 10^3 です 多重辺確かにあった方がいいなということで、そうした場合 M の上限を増やしたほうがよかったりしますか？(多重辺作問した事がなく、その場合の辺数の相場が分かりません。特にないということであれば 10^3 です)

[yosupo06]

頂点数, 辺数, Kは最終的には実行時間見て調整したいところではありますが、N = Mで問題ないです！(2 * N = M ぐらいに設定する人もいますが、ぶっちゃけwriterの趣味嗜好だと思っています)

以下にいくつか些細なコメントをしておきます

問題名/ID: どうやらk-shortest pathと書いたときに同じ頂点を通れるかどうかが曖昧っぽいです(https://en.wikipedia.org/wiki/K_shortest_path_routing#Loopless_variant )。pathって書いたらsimple pathだろとは思うのですが、(K Shortest Loopless Paths / k_shortest_loopless_paths)とかにしてわかりやすくしてほしいです

入力形式: グラフ部分については https://judge.yosupo.jp/problem/shortest_path と同じがいいと思います

出力形式: パスの個数が足りなかったら-1を出力を想定していると思います、それで大丈夫です。

[null0124]

コメントありがとうございます！諸々了解しました。 その上で、いくつか質問 (相談) させてください

1. グラフは非連結のほうがよかったりしますか (最初に普通の dijkstra を回すのでどちらでもよさそうですが)
2. 経路の出力をさせたほうがいいですか (どちらにせよ経路を求めるのでどちらでもよさそうですが 2)
3. simple か loopless かで悩んでいます。simple の方が一般的？らしく google 検索の量も断然多いのですが、元論文は loopless で...

[yosupo06]

1. 連結とは限らない、でいいと思います
2. どちらでも大丈夫ですが、させなくていい気がします(shortest pathは構築をさせていて、K-Walk ShortestはK=100,000で構築が不可能なので、微妙なところ…)
3. simpleのほうが有名ならそっちにしましょう

[maspypy]

議論はひとまず終わっているように見えるので、作業者募集です。