共通の頂点を持たないグラフの上位K個のパスを負の重みで見つけるアルゴリズム？

Question

ベルマンフォードを使用して、負の重みを持つグラフの最短経路を探しています。このグラフには、ループの可能性はなく、双方向接続もありません。私は、パスが共通のノードを共有していないグラフからK個の最短経路を探したいと思う。私はこれを行う方法を学ぶために探すことができるアルゴリズムはありますか？現時点では、スピードよりも単純な実装が重要です。

追加：コメントありがとうございます。明確にするために、私は指定された開始ノードから指定された終了ノードに至る最上位のKの方法を探しています。他のノードは共通していません。グローバルな最適化が必要です。ノードを順番に見つけて削除することは満足のいく結果をもたらさない。この1つ：https://en.wikipedia.org/wiki/Yen%27s_algorithmは、私が話していることの味を与えますが、この場合、負のエッジコストを必要とせず、ノードを共有することもできます。

Answer 1

私はこの問題が最小コストフローを見つけることで解決できると思います。

のは、次のようにグラフを変換してみましょう：

1. は、ソース以外の各ノードVを交換して、二つのノードV1 とから重み0のエッジによって接続されたV2とシンクv1~v2。前者Vの 着信縁V1に入り、V2から発信 休暇。この問題は、これらのエッジを複数回使用しないことに相当します。

2. すべてのエッジに容量1を設定します。

Kはあなたに（なぜなら、これらの新しいエッジで1に容量を置くの）ノードを共有しないKパスを与える価値の流れを見つけます。したがって、このフローが最小コストフローであれば、それらのパスには最小限のコスト総額があることがあります。K

これは、ソースとシンクを直接接続するエッジがないことを前提としています。そのコーナーケースを個別に確認してください。