可能な重複を別個のパスの数を見つけるために:
Graph Algorithm To Find All Connections Between Two Arbitrary Verticesアルゴリズムは有向グラフで
Iは有向グラフを持って、私は、別個の番号を見つけるために使用できるものアルゴリズム2つの特定の頂点間の非周期的なパス、およびこれらの異なるパスで使用されるパスの最大回数を数えます。 異なる数の頂点を訪問するか、別の順序で頂点にアクセスすると、2つのパスが区別されます。
可能な重複を別個のパスの数を見つけるために:
Graph Algorithm To Find All Connections Between Two Arbitrary Verticesアルゴリズムは有向グラフで
Iは有向グラフを持って、私は、別個の番号を見つけるために使用できるものアルゴリズム2つの特定の頂点間の非周期的なパス、およびこれらの異なるパスで使用されるパスの最大回数を数えます。 異なる数の頂点を訪問するか、別の順序で頂点にアクセスすると、2つのパスが区別されます。
少し修正されたDijkstraのアルゴリズムに従えば、すべての対の解を持つことができます。
説明:w
通過w
u
からv
た:v
からu
からのパスは、以下の合計でありますu
からw
からのパス数w
からv
i
からj
(1)のエッジがある場合を除いて、ゼロで行列を初期化します。 は、その後、次のアルゴリズムは、(すべてのペアパスカウント)言うまでもなく
for i = 1 to n:
for j = 1 to n:
for k = 1 to n:
paths[i][i] += paths[i][k] * paths[k][j]
あなたに結果を与える:O(n^3)
シングルペア・ソリューションを読むことを熱望。 :)
この解決策では、パスにサイクルがない必要があるという要件を正しく処理できません。 – hugomg
これは変更されたBellman-Fordであり、変更されたDijkstraではありません(したがってサイクルの問題)。 –
IMHOこれは重複する必要はありません。値の数を知ること(整数)とすべての値(ノードのリストの集合)を知ることには違いがあります。私の目的のために、数字(上限)の妥当な推測さえもOKですので、私にとってこれは重複しません。 – danatel
[2つの任意の頂点の間のすべての接続を見つけるためのグラフアルゴリズム](http://stackoverflow.com/q/58306)は全く重複しません。列挙とカウントは異なる問題です。有向グラフは、無向グラフ。単純なパスの計算の複雑さについては、[有向グラフの2ノード間の単純なパスの数をどのように数えるのですか?](http://cs.stackexchange.com/q/423)の[cs.se]を参照してください。 – Gilles
私はDanatelに同意します。大きなグラフの場合は、すべての可能なパスの列挙を数えるのは望ましくありません。 –