次の問題があります。私は循環的で無向の加重グラフ G=(V,E) を持っています。次のルールに従って、指定された 2 つのノード間の単純なパス (サイクルなし) を見つける必要があります。
- 各可能なパスのエッジセットで最小の重み値を見つける
- 見つかったパスから選択された最小値の中で最大の最小値を持つこのパスを選択します
たとえば、以下に示すグラフがあります。
ノード 1 からノード 8 への単純なパスを見つけることができます。次に示す 2 つのパスが考えられます。
- 1 -> 3 -> 5 -> 8、このパスの最小エッジ ウェイトは 2 です
- 1 -> 3 -> 5 -> 6 -> 7 -> 8、このパスの最小エッジ ウェイトは 283 です。
提示された基準によると、必要なパスはパス番号 2 です。これは、パス番号 1 よりも最小値が大きいためです。
1 つの重要な仮定: グラフ内のノードの数は非常に少なく、15 未満です。
Dijkstra または Bellman-Ford アルゴリズムの変更について考えましたが、課題は、ローカル基準 (最小距離) がないことです。パス全体を取得しない限り、エッジの最小の重みを見つけることができません...
私の 2 番目の考えは、Nearest-Neighbor アルゴリズムの修正を使用することでしたが、これは、いわゆる巡回セールスマン問題を解決するために使用されます。これは、私の場合とは少し異なります。
私の質問は次のとおりです。この問題を解決するには、Depth-First Algorithm を使用して 2 つの特定のノード間のすべての直接的な非巡回単純パスを取得し、次に見つかった各パスの最小重み値の最大値を選択するよりも良い方法はありますか?
そのような場合、特に再帰とグラフ内の可能な接続 (エッジ) の数のために、DFS アルゴリズムの複雑さが少し心配です。
アイデアをありがとう。