パスの「長さ」は、パス内のエッジの数です。
ソースとデスティネーションの頂点が与えられた場合、ソースの頂点から与えられた長さkのデスティネーションの頂点までのパスの数を見つけたいと思います。
各頂点には何度でもアクセスできるため、から
a
へのパスb
が次のようになっている場合、a -> c -> b -> c -> b
それは有効であると見なされます。これは、サイクルが存在する可能性があり、目的地を複数回通過できることを意味します。2つの頂点を複数のエッジで接続できます。したがって、頂点
a
と頂点が2つのエッジで接続されている場合、エッジ1とエッジ2を経由b
するパスは異なると見なされます。a -> b
a -> b
頂点の数Nは<=70であり、パスの長さであるKは<= 10^9です。
答えは非常に大きくなる可能性があるため、いくつかの数値を法として報告されます。
これが私がこれまでに考えたことです:
頂点を訪問済みとしてマークせずに幅優先探索を使用できます。各反復で、そのパスに必要なエッジの数「n_e」と、各エッジの各エッジの重複エッジの数の積「p」を追跡します。パスがあります。
n_e
がkより大きい場合、検索検索は終了する必要があります。kn_e
に等しい宛先に到達した場合は、検索を終了し、p
パス数を追加します。
最短経路は必要なく、幅優先探索で使用されるQのサイズが十分でない可能性があるため、幅優先探索の代わりに深さ優先探索を使用できると思います。
私が考えている2番目のアルゴリズムは、このアプローチを使用したFloydWarshallのアルゴリズムに似ています。最短経路は必要ないので、これが正しいかどうかはわかりません。
私が最初のアルゴリズムで抱えている問題は、「K」が最大1000000000になる可能性があることです。つまり、検索は10 ^ 9のエッジがあり、各レベルでエッジ数が1ずつ増えるまで検索が実行されます。遅く、大きな入力で終了するかどうかはわかりません。
したがって、この問題を解決するには別のアプローチが必要です。どんな助けでも大歓迎です。