トラバースしたい有向非循環加重グラフがあります。
有効なソリューション ルートの制約は次のとおりです。
通常、グラフには大量の頂点とエッジがあるため、すべての可能性を試すことはオプションではなく、非常に効率的なアルゴリズムが必要です。
この問題に対するいくつかのポインタまたは適切なアルゴリズムを探しています。ダイクストラのアルゴリズムを使用して最初の条件が簡単に満たされることはわかっていますが、2 番目の条件を組み込む方法や、どこから調べればよいかさえわかりません。
追加情報が必要な場合はお知らせください。
グラフ内の長さNのパスに関心があるのか、それとも 2 つの特定の頂点間のパスに関心があるのかはわかりません。後者だと思いますが、質問でその制約について言及していませんでした。
前者の場合、ソリューションは自明なダイクストラのようなアルゴリズムである必要があります。このアルゴリズムでは、すべてのエッジを潜在的なパス値で並べ替えます。この値は、エッジの重みで始まり、既に構築された隣接パスによって調整されます。各反復で、最良の潜在的なパス値を持つノードを取得し、隣接するパスに追加します。長さ N (または側面で切り取った長さ) のパスが得られたら停止します。他にもいくつかの技術的な詳細があります。に関して。長いパスを作成しますが、これはあなたが興味を持っているものではないと思われるため、詳細には触れません. :-)
ソースとシンクが固定されている場合、深い魔法は関係ないと思います。キューに追加された各頂点にパスが関連付けられる基本的な Dijkstra を実行するだけで、パスの長さ >= N の頂点をキューに挿入しないでください。パス長が N でない限り、シンクをキューに挿入しません。