無向加重完全グラフで最大コストが与えられた場合、最小コストと最大長を持つ 2 つのノード間のパスを見つけるアルゴリズムを探しています。重みは負ではありません。
現在、私はDFSを使用していますが、かなり遅いです（ノード数が多く、最大長も長い）。DFS の反復ごとに、不可能なノードをすべて破棄しています。
この問題をより適切に処理するための既知のアルゴリズムを教えてもらえますか?
明確にするために：理想的には、アルゴリズムは最小コストのパスを検索する必要がありますが、これがより多くのノードを訪問することを意味する場合は、コストを追加することができます。コスト制限を超えずに n 個を超えるノードに到達することは不可能であり、より少ないコストで n 個のノードに到達することは不可能であると結論付けたときに終了する必要があります。
アップデート
グラフの例。A から B に移動する必要があります。コスト制限は 5 に設定されています。
このパス (赤) は問題ありませんが、アルゴリズムはより良い解決策を探し続ける必要があります
コストは 4 に増えますが、ノードが 1 つ増えるため、これは優れています。
ここでは、パスに 3 つのノードが含まれているため、以前よりもはるかに優れており、コストは許容範囲内です 5
最後に、このソリューションはさらに優れています。パスにも 3 つのノードが含まれていますが、コストが 4 で、以前よりも少ないためです。
画像がテキストよりもうまく説明できることを願っています