1

Floyd-Warshall アルゴリズムを実装しました。それらの行列によると、2 つの場所の間の最短経路とその距離について、正しい結果を得ることができます。私の質問は、i から j までの最短距離を出力する方法です。私はいくつかの調査を行い、そのようなアルゴリズムを見つけました。誰かが私にそれがどうあるべきか、またはどのように機能するかを説明できますか、または他の提案を言うことができますか?

PrintShortestPath(P,i,j){
    if(i==j) print i
    else if (P[i][j]==NULL)
        print "No path from i to j"
    else{
        PrintShortestPath(P,i,P[i][j])
        print j
    }
}
4

2 に答える 2

1

Floyd のアルゴリズムは、2 つのノード間のすべてのパスを考慮し、これまでに見つかった最も安価なものを保持します。あなたのコードはこれを再帰的に処理します。これは、Cでこれについて適切に説明された別の実装です: http://www.fearme.com/misc/alg/node88.html

また、まばらなグラフのパフォーマンスが向上するダイクストラのアルゴリズムを検討することもできます。

--L.

于 2012-06-11T09:11:04.103 に答える
0

投稿したアルゴリズムの行列 P は、先行行列です。すべてのパス i -> j の前身がリストされます。

これは、距離行列と一緒に計算する必要があります。

  • P[i,j] はすべての i,j に対して NULL に初期化されます
  • FW の最も内側のループで、ノード k から通過する短いパスが見つかった場合は P[i,j] を更新します (P[k,j] を使用)。

距離のソリューションを投稿すると、より正確になります。

于 2013-05-06T21:58:57.667 に答える