重み付けされていない有向アシル グラフが与えられた場合、Floyd-Warshall アルゴリズムを適応させて、2 つの頂点間のパスの数をカウントしようとしています。私のコードは現在次のようになっています。
1 から n のすべての k に対して 1 から n のすべての i に対して 1 から n のすべての j に対して Aij = Aij + (Aik * Akij)。
したがって、最小距離を確認して置き換える代わりに、次のことを行っています。
i( , j)間のパスのk数 + ( からのパスのカウント * からのパスiのカウント)kkj
私の最終的な配列には、任意の 2 つの頂点間のパスの数が必要です。
これが 2 つの頂点間の単純なパスの数を与えないことを証明することはできませんが、このアプローチを他の場所で使用する提案はありません。
誰かがこれが失敗する反例を提供できますか?
PS: これは私の宿題ではなく、私が取ったプログラミングの演習です。
無向の重み付けされていないアシルグラフでは、任意の2つの頂点間に最大で1つのパスがあります。より明確なパスがあれば、それらはサイクルを作成します。 （質問が編集された後は関係ありません）
有向グラフの場合、アルゴリズムに問題はありません。修正されたFloyd-Warshallアルゴリズムの使用法は、この論文で実際に言及されています。広く使用されていない理由は、おそらくその複雑さです-この単純なアプローチのO（m + n）と比較したO （n 3 ）
巡回グラフの場合、単純なパスをカウントするには、どこに行ったかを追跡する必要があるため、単純な Floyd-Warshall アルゴリズムではこれを行うことができません。動的計画法では、計算される状態は再帰の状態の関数のみであると想定していますが、この場合はそうではありません。
しかし、なぜこれがうまくいかないのかわかりません。しかし、Floyd-Warshall を使用して 2 つの頂点のみを計算するのはなぜですか (DFS または BFS を使用するだけです)。