algorithm - グラフ内の2つの指定されたノード間の指定された長さのすべてのパス

Question

私はこの問題に遭遇しました：

http://www.iarcs.org.in/inoi/contests/oct2005/Advanced-2.php

問題は基本的にグラフに関するものです。最大70個のノードを含むグラフと、2つのノード間に存在するエッジの数を示す隣接行列が表示されます。各エッジは双方向です。

ここで、質問は、任意の2つのノードN1とN2の間の固定長Nの個別のパスの数を見つけるように求めます。パスは繰り返しを持つことができます。つまり、パスはすでに含まれているノードを通過できます。

最も重要なアルゴリズムは、幅優先探索を実行し、N1をルートとするBFSツリーを使用してN番目のレイヤーに表示されるN2の数を確認することです。しかし、これは機能しません。

それについてどうやって行くのですか？

Answer 1

この問題の解決策は簡単です。隣接行列を N 乗すると、(N1, N2)N1 と N2 の各ペアのセルに答えが格納されます - 基本的なグラフ理論です。

行列の2 進累乗を使用して、答えをより速く計算することもできます。

上記のアルゴリズムが機能する理由を理解するために、累乗の最初の数ステップを書き留めてみてください。各反復で、行列が 1 から N までの特定の固定長のパスを保持していることに気付くでしょう。行列の乗算を実行するときにセルがどのように計算されるかを書き留めると、なぜそうなるのかもわかるはずです。

注: 固定長までの長さのすべてのパスを計算する方法についての非常にクールなハックもあります。開始頂点に「ループ」を追加するだけで、それ自体からアクセスできるようになります。