5

プリムのアルゴリズムとダイクストラのアルゴリズムの違いを知っています。前者は MST を生成し、後者はソースからすべてのノードへの最短パスを提供します。数学的には、これらは同じではないため、2 つのアルゴリズムが常に同じ結果を生成するとは限りません。

ただし、さまざまな例を試してみると、同じ結果が得られます。Prim のアルゴリズムと Dijkstra のアルゴリズムの疑似コードも非常によく似ています。Prim が生成する MST が、Dijkstra で解決しているときに得られない、またはその逆の例を教えてください。

また、私の知識によると。これらのアルゴリズムは両方とも、次のアプローチを使用します。私が間違っている場合は修正してください：

すでに含まれているセットの i とまだ含まれていないセットの j で最短の ij を見つけ、j をセットに追加します。

4

2 に答える 2

5

単純な例は、正方形の角に配置された 4 つのノードのコレクションです。隣接する 2 つの角の間にコスト 2 の辺を配置し、正方形を斜めに横切るようにコスト 3 の辺を配置します。任意のコーナーから Dijkstra のアルゴリズムを実行すると、次のエッジが選択されます。

* -- *
| \
|  \
*    *

これらは最短パスで、エッジの合計コストは 7 です。

Prim のアルゴリズムを実行すると、次のエッジが選択されます。

* -- *
| 
|
* -- *

これは MST (合計エッジ コストは 6) ですが、これらは最短パスではありません (左上隅から右下隅へのパスのコストは 4 ですが、より直接的なルートが可能です)。

課題として: グラフを見つけてみてください。

  • ダイクストラのアルゴリズムは、実際の MST よりも Ω(n) 倍重い最短パス ツリーを見つけます。
  • Prim のアルゴリズムは、ツリー内のパスが対応する最短パス ツリー内のパスよりも Ω(n) 倍長い MST を見つけます。

Prim と Dijkstra はどちらも、セットにないノードを見つけてセットに入れることでノードを選択しますが、距離を調整する方法が異なります。Prim のアルゴリズムでは、使用される距離は常に、セット外の任意のノードからセット内の任意のノードまでの最小距離です。ダイクストラのアルゴリズムでは、距離は次の値の最小値です。

距離(開始ノード, u) + l(u, v)

言い換えれば、Dijkstra のアルゴリズムは、開始ノードからセット外のノードまでの距離を考慮しますが、Prim のアルゴリズムは考慮しません。

お役に立てれば！

于 2013-10-13T19:50:23.533 に答える