私はFloyd-Warshallアルゴリズムを適用して、2つの頂点間のパス数を数えようとしています。私のコードは、現在、次のようになります。Floyd-Warshallアルゴリズムを使用して2つの頂点の間のパス数を計測する
すべてのkについて1中のn にすべてのために私は1にn個 に、すべてのjについて1でnに Aijを= Aijを+（AIK * Akij）。 k + iからkへのパスの（カウント*からのパスの回数なし（i、j）間のパスの
数：
はそのため、代わりにチェックすると分の距離のために置き換えるので、私は次のことをやっていますk * j）
最後の配列は、任意の2つの頂点間のパス数を持つ必要があります。
2つの頂点の間の単純なパスの数がわかりませんが、このアプローチを他の場所で使用する方法はありません。
誰かがこれが失敗した場合のカウンタの例を提供できますか？
PS：これは私の宿題ではありませんが、私が拾っただけのプログラミング演習です。
無記名の非重み付きアシリックグラフでは、任意の2つの頂点の間に最大で1つのパスがあります。より明確なパスがあれば、サイクルを作ります。
（質問が編集された後には関係ありません）有向グラフの場合、私はあなたのアルゴリズムに問題が表示されません。修正Floyd-Warshallアルゴリズムの使用法は実際にはthis paperに記載されています。それは、広く使用されていない理由は、おそらく、その複雑である - O（N ）巡回グラフの場合にはO this simple approach
私は誤字謝罪します。私は有向グラフを指していました。元の投稿の間違いを修正しました。 –
偉大な、私は必要なものを紙に説明します。私はまた、紙に書かれているように、対角要素の結果がゼロではないことを捨てることができると仮定しました。 –
の（+ N M）と比較して、あなたは直フロイド・ウォーシャルでこれを行うことはできませんアルゴリズムを使用する必要があります。シンプルなパスを数えるためには、どこにいたのかを把握する必要があります。動的計画法では、計算されている状態は再帰の状態の関数にすぎないと仮定していますが、この場合は真ではありません。
しかし、私はこのがなぜでないのかわかりません。しかし、なぜFloyd-Warshallを使って2つの頂点だけを計算するのですか（単にDFSかBFSを使用します）。
はい、DFS/BFSを使用できます。しかし、Floyd-Warshallの使用の正当性をチェックしたかったのです。また、サイクルの場合、計算の終わりに、対角要素のいずれか1つがゼロ以外の値になる可能性がある場合、結果を破棄することができます。繰り返しますが、私はこれが最も効率的ではないことを理解しています。 –
「2つの頂点の間の単純なパスの数がわからないことを証明することができません。何も意味しません。確かに正しいかどうかを知るためには、そうでないことを示す反例を見つけることができます。 – amit