指示されたグラフの指定された長さ未満のすべてのパスは、2つのノード間の間にあります

Question

指示されたグラフまたは無向グラフのいくつかのノードの間に、可能なすべてのパス、または特定の長さのすべての可能なパスをカウントすることは、古典的な問題です。何に注意を払うべきです すべて 可能性のあるサイクルのために、意味します。

この質問はわずかに異なります、または少なくとも私は思います。

入力： なれ g 指示されたグラフ。 g サイクルと自己接続ノードを持つことができます。させて A（g） の隣接マトリックスになります g （1インチがあります g_I、J IからJへのリンクがあり、それ以外の場合はa 0にリンクがある場合）。定義 t と b のノードの2つのサブセット g, 、おそらくボイド交差点で。

結果： 長さのすべてのパスのリスト せいぜい kは1つのノードから移動します t 1つのノードに b. 。パスは、ソースノードからターゲットノードにターゲットノードに固くK+1ステップ未満で移動する限り、同じエッジを複数回含めることができます。

質問： このタスクでどのアルゴリズムが最適かを知りたいです。隣接マトリックスのn番目の電力が象徴的に計算された場合（1の代わりに各エントリの異なる変数がある場合）、このすべてのパスのトラックを保持するという事実に基づいて、可能な答えを開発しようとしています（そしてそれはエントリの1で数値的に計算された場合、パスのカウントに減少します）。しかし、これがタスクを実行する最速の方法であるかどうかは本当にわかりません（おそらくそうではありません）。

警告： 私はカウントの問題を求めていませんし、最も短いパスについても、パスの長さは使用されるエッジの数として定義されます（繰り返しをカウント）。私はrを使用していますが、他の言語でそれについて考えたいなら！質問がすでに提起され、解決されていれば本当に申し訳ありません。親切な助けをありがとう！

追加情報： マトリックスパワーシリーズアプローチ（A^3は3つの長いパスすべてを与えます...）とDFS / BFSを試しました。後者の2つは、私がソースとターゲットのセットに取り組んでいると考えていないので、多くの冗長な仕事をしていることを考慮に入れていないので、最適性とはほど遠いと思います...

Answer 1

私があなたの質問について何かを見逃していない場合は、複数のソースと目的地に関する質問を単一のソースと単一の宛先の場合に減らすための標準的なトリックを適用できます。

1. 2つの新しいノード$ s $と$ t $を追加します。
2. $ s $をすべてのソースに接続し、
3. すべての宛先を$ t $に接続します。

この削減後、私たちは2つの追加の頂点$ s $と$ t $を備えた標準的な質問設定にあり、最大$ k+2 $で$ s $から$ t $の散歩を見つけたいと考えています。