グラフ理論、与えられた距離を持つすべてのパス

Question

私は、旅行者がある距離をグラフで移動でき、すべての双方向エッジがある長さ（距離）を持つ問題を発見しました。特定のエッジ（いずれかの方向）を走行すると、あなたはあなたが旅行することができます与えられた距離のために収集することができる最大のお金を見つける必要があるので、いくつかのお金/ギフト（それはすべてのエッジのために問題になっている）を得ると仮定する。基本的な問題は、与えられた距離（グラフ内にループが存在する可能性があります）で可能なすべてのパスを見つける方法と、すべての可能なパスを見つけた後、収集される最大金額のパスが単純に答えになることです。注：考えられる可能性のあるパスは、ループ（直線パス）を持たないようにしてください。

Answer 1

エッジ（距離と報酬）に二重重みを持つ無向グラフが与えられます。 可能な距離に対応する固定数dが与えられます。

ノードの各対（u、v）は、uがVに等しい、あなたがその合計距離dはない繰り返すノードとuとvとを結ぶ

• すべてのパス{P_j}を探していないため。
• 報酬が最大である{P_j}の部分{P_hat（j）}の部分集合。

最初に取得するには、Floyd-Warshallアルゴリズムの修正バージョンを使用します。ここでは、最短ではなく、任意のパスを探します。 Floyd-Warshallは、uとvの間の「中間ノード」wを考慮した戦略を使用し、uとvの距離を最小限にするパスを再帰的に見つけます。

すべてのパスを除外inf距離行列に既に訪問しているノードを実行時に除外し、距離がdよりも長いか、最後に到達する（uとvを結ぶ）再帰の部分パスをすべて除外します。距離がdよりも短い。

この2番目の場合のように、常に1つの値dの代わりに可能な間隔[d、D]が与えられれば一般化できます。空のセットが常に得られます。

2番目の手順では、最初の手順の解決で見つかった各パスの報酬を単純に比較して、最適なものを取るだけです。

完全な回答ではなく、より多くの方向性がありますが、それが助けてくれることを願っています！