116

ダイクストラのアルゴリズムとプリムのアルゴリズムの正確な違いは何ですか? PrimがMSTを提供することは知っていますが、Dijkstraによって生成されたツリーもMSTになります。それでは、正確な違いは何ですか？

4

16 に答える 16

168

Prim のアルゴリズムは、グラフの最小スパニング ツリーを構築します。これは、グラフ内のすべてのノードを接続し、すべてのノードを接続するすべてのツリーの中で最小の総コストを持つツリーです。ただし、MST 内の任意の 2 つのノード間のパスの長さは、元のグラフ内のこれら 2 つのノード間の最短パスではない場合があります。MST は、たとえば、グラフ内のノードを物理的に配線して、最小の総コストで電力を供給したい場合に役立ちます。2 つのノード間のパスの長さが最適でなくてもかまいません。関心があるのは、それらが接続されているという事実だけだからです。

ダイクストラのアルゴリズムは、あるソース ノードから始まる最短パス ツリーを構築します。最短パス ツリーは、グラフ内のすべてのノードをソース ノードに接続するツリーであり、ソース ノードからグラフ内の他のノードへのパスの長さが最小化されるというプロパティがあります。これは、たとえば、誰もが主要な重要なランドマークに到達するのをできるだけ効率的にする道路網を構築したい場合に役立ちます。ただし、最短パス ツリーが最小スパニング ツリーであるとは限りません。最短パス ツリーのエッジのコストの合計は、MST のコストよりもはるかに大きくなる可能性があります。

もう 1 つの重要な違いは、アルゴリズムが処理するグラフの種類に関するものです。Prim のアルゴリズムは、MST の概念がグラフが本質的に無向であると想定しているため、無向グラフでのみ機能します。(有向グラフには「最小スパン アーボレッセンス」と呼ばれるものがありますが、それらを見つけるアルゴリズムははるかに複雑です)。ダイクストラのアルゴリズムは有向グラフでうまく機能します。さらに、ダイクストラのアルゴリズムは、負の辺の重みを含むグラフで必ずしも正しい解を生成するとは限りませんが、プリムのアルゴリズムはこれを処理できます。

お役に立てれば！

于 2013-01-03T18:41:11.657 に答える
94

ダイクストラのアルゴリズムはMSTを作成せず、最短経路を見つけます。

このグラフを検討してください

       5     5
  s *-----*-----* t
     \         /
       -------
         9

最短パスは9ですが、MSTは10の別の「パス」です。

于 2013-01-03T17:52:35.523 に答える
56

Dijsktra のアルゴリズムは、ノード i からすべてのノード(i を指定) までの最小距離を見つけます。その見返りに、ノード i から最小距離ツリーを取得します。

Prims アルゴリズムは、特定のグラフの最小スパニング ツリーを取得します。すべてのノードを接続し、すべてのコストの合計が最小になるツリー。

したがって、ダイクストラを使用すると、選択したノードから最小コストで他のノードに移動できますが、プリムのノードではこれが得られません

于 2012-12-10T04:27:02.193 に答える
33

私が見る唯一の違いは、プリムのアルゴリズムが最小コストエッジを格納するのに対し、ダイクストラのアルゴリズムはソース頂点から現在の頂点までの合計コストを格納することです。

ダイクストラは、コストが最小になるように、ソースノードから宛先ノードへの道を提供します。ただし、Primのアルゴリズムは、すべてのノードが接続され、総コストが最小になるように、最小スパニングツリーを提供します。

簡単に言えば：

したがって、複数の都市を接続するために列車を配備する場合は、プリム法を使用します。ただし、ある都市から別の都市に移動してできるだけ時間を節約したい場合は、ダイクストラのアルゴを使用します。

于 2012-12-10T04:27:24.397 に答える
26

どちらも、次のようにまったく同じ汎用アルゴリズムを使用して実装できます。

Inputs:
  G: Graph
  s: Starting vertex (any for Prim, source for Dijkstra)
  f: a function that takes vertices u and v, returns a number

Generic(G, s, f)
    Q = Enqueue all V with key = infinity, parent = null
    s.key = 0
    While Q is not empty
        u = dequeue Q
        For each v in adj(u)
            if v is in Q and v.key > f(u,v)
                v.key = f(u,v)
                v.parent = u

Prim の場合は pass f = w(u, v)、Dijkstra の場合は passf = u.key + w(u, v)です。

もう 1 つの興味深い点は、上記の Generic は幅優先検索 (BFS) も実装できることですが、高価な優先キューは実際には必要ないため、やり過ぎになります。上記のジェネリック アルゴリズムを BFS に変換するには、f = u.key + 1すべての重みを 1 に強制するのと同じパスを渡します (つまり、BFS は、ポイント A から B にトラバースするために必要なエッジの最小数を指定します)。

直感

上記の一般的なアルゴリズムについて考える 1 つの良い方法を次に示します。2 つのバケット A と B から始めます。最初に、バケット A が空になるように、すべての頂点を B に入れます。次に、1 つの頂点を B から A に移動します。次に、A の頂点から B の頂点に交差するすべてのエッジを調べます。これらの交差エッジからいくつかの基準を使用して 1 つのエッジを選択し、対応する頂点を B から A に移動します。 A. B が空になるまでこのプロセスを繰り返します。

このアイデアを実装する強引な方法は、B に交差する A の頂点のエッジの優先キューを維持することです。グラフがまばらでない場合、明らかに面倒です。質問は、代わりに頂点の優先キューを維持できるかということです。実際、B からどの頂点を選択するかが最終的に決定されるので、これは可能です。

歴史的背景

興味深いことに、両方のアルゴリズムの背後にある技術の一般的なバージョンは、概念的には、電子コンピューターが存在していなかった 1930 年と同じくらい古いものです。

物語は、Otakar Borůvka が家族の友人のためにアルゴリズムを必要としていたことから始まります。彼は、モラビアの国 (現在はチェコ共和国の一部) の都市を最小コストの送電線で接続する方法を見つけようとしています。彼は 1926 年に数学関連のジャーナルにアルゴリズムを発表しました。当時はコンピューター サイエンスが存在していなかったからです。これは Vojtěch Jarník の注意を引き、Borůvka のアルゴリズムの改良を考えて 1930 年に公開しました。実際、彼は、1957 年に再発見された Prim のアルゴリズムとして現在知られているものと同じアルゴリズムを発見しました。

これらすべてとは別に、1956 年にダイクストラは、彼の研究所が開発した新しいコンピューターの機能を実証するためのプログラムを作成する必要がありました。彼は、コンピューターがオランダの 2 つの都市間を移動するための接続を見つけたらクールだと考えました。彼は 20 分でアルゴリズムを設計しました。彼は 64 の都市のグラフをいくつか単純化して作成し (彼のコンピューターは 6 ビットだったため)、この 1956 年のコンピューター用のコードを書きました。しかし、彼は自分のアルゴリズムを公開しませんでした。これは、主にコンピューター サイエンスのジャーナルがなく、これはあまり重要ではないと考えたためです。翌年、彼は、ワイヤの長さが最小限になるように新しいコンピューターの端子を接続する問題について学びました。彼はこの問題について考え、Jarník/Prim' を再発見しました。このアルゴリズムは、彼が 1 年前に発見した最短経路アルゴリズムと同じ手法を再び使用します。彼彼のアルゴリズムは両方とも、ペンや紙を使用せずに設計されていると述べました。1959 年に、彼は 2 ページ半の論文で両方のアルゴリズムを発表しました。

于 2014-12-30T05:40:17.657 に答える
15

Dijkstra は、開始ノードと他のすべてのノードの間の最短パスを見つけます。その見返りに、最初のノードから最小距離ツリーを取得します。つまり、他のすべてのノードにできるだけ効率的に到達できます。

Prims アルゴリズムは、与えられたグラフ、つまりすべてのノードを接続するツリーの MST を取得しますが、すべてのコストの合計は可能な限り最小になります。

現実的な例で話を短くするには:

  1. Dijkstra は、移動時間と燃料を節約して、各目的地への最短経路を知りたいと考えています。
  2. Prim は、鉄道レール システムを効率的に展開する方法、つまり材料費を節約する方法を知りたがっています。
于 2013-01-04T06:04:19.110 に答える
10

ダイクストラのアルゴリズムのウィキペディアの記事から直接：

ダイクストラのアルゴリズムの基礎となるプロセスは、プリムのアルゴリズムで使用される貪欲なプロセスに似ています。Primの目的は、グラフ内のすべてのノードを接続する最小スパニングツリーを見つけることです。ダイクストラは2つのノードのみに関係しています。Prim'sは、開始ノードからのパスの合計の重みを評価せず、個々のパスのみを評価します。

于 2013-01-03T17:50:25.477 に答える
3

Dijkstra のアルゴリズムはノード i と j の間の単一ソース最短経路問題ですが、Prim のアルゴリズムは最小スパニング ツリー問題です。これらのアルゴリズムは、「貪欲なアルゴリズム」という名前のプログラミング概念を使用します

これらの概念を確認したら、アクセスしてください

  1. 貪欲アルゴリズム講義ノート : http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf
  2. 最小全域木 : http://jeffe.cs.illinois.edu/teaching/algorithms/notes/20-mst.pdf
  3. 単一ソースの最短パス: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/21-sssp.pdf
于 2012-12-10T04:22:55.450 に答える
0

@templatetypedef は、MST と最短パスの違いをカバーしています。アルゴリズムの違いについては別の記事で説明しましたので、入力としてもう1つのパラメーターを取る同じ汎用アルゴリズムを使用して両方を実装できることを示して答えf(u,v)てください: function 。Prim と Dijkstra のアルゴリズムの違いは、単純にどちらf(u,v)を使用するかです。

于 2014-12-30T04:07:34.233 に答える