Johnson Algorithmの有用性を理解するのに苦労しています。この分野の知識を持っている人にとっては、この質問は本当にばかげているように聞こえるに違いないと思いますが、私には理解できません。ウィキペディアによると、ジョンソン アルゴリズムはベルマン フォード アルゴリズムを使用してエッジの重みを非負の重みに変換し、ダイクストラ アルゴリズムを使用して最短経路を見つけます。しかし、ベルマンフォードアルゴリズムも最短経路を見つけるアルゴリズムです。Bellman Ford Algorithm から取得した最短経路を使用しないのはなぜですか?
2397 次
3 に答える
8
Bellman-Fordアルゴリズムは、単一のソースからすべてのグラフ頂点への最短パス（「単一ソースの最短パス」）を見つけます。ジョンソンのアルゴリズムは、すべての頂点から他のすべての頂点への最短経路（「すべてのペアの最短経路」）を見つけるため、グラフ内のすべての可能な開始頂点からベルマンフォード法を実行するのと同じです。
于 2011-03-15T19:11:05.630 に答える
1
私はこのパーティーに遅れていることを知っていますが、同じことを自問していたので、この質問に出くわしました.
理解を深めるために、ジョンソンのアルゴリズムの最初のステップで実際に新しいグラフが作成されることを指摘したいと思います。これは、Bellman-Ford アルゴリズムを巧みに使用して元のグラフ (負のエッジを持つ可能性がある) を、負のエッジを持たない別の (ただし同等の) グラフに変換することによって行われます。この新しいグラフは、Dijkstra のアルゴリズムで安全に使用できるようになりました。次に、ダイクストラのアルゴリズムを使用して、他の2つの回答で言及されている「すべてのペアの最短パス」を効率的に計算します。
わかりやすい説明がここにあります: http://www.geeksforgeeks.org/johnsons-algorithm/
于 2015-01-12T16:28:34.953 に答える