Prim과 Dijkstra의 알고리즘의 차이점은 무엇입니까?

Prim과 Dijkstra의 알고리즘의 차이점은 무엇입니까?

---

Dijkstra와 Prim의 알고리즘의 정확한 차이점은 무엇입니까? 나는 Prim이 MST를 줄 것이라는 것을 알고 있지만 Dijkstra가 생성 한 트리도 MST가 될 것입니다. 그렇다면 정확한 차이점은 무엇입니까?

---

Prim의 알고리즘 은 그래프 의 최소 스패닝 트리 를 구성하는데 , 이는 그래프의 모든 노드를 연결하는 트리이며 모든 노드를 연결하는 모든 트리 중에서 총 비용이 가장 적습니다. 그러나 MST에서 두 노드 사이의 경로 길이는 원래 그래프에서 두 노드 사이의 최단 경로가 아닐 수 있습니다. 예를 들어, 그래프의 노드를 물리적으로 연결하여 최소 총 비용으로 노드에 전기를 공급하려는 경우 MST가 유용합니다. 두 노드 사이의 경로 길이가 최적이 아닐 수도 있다는 것은 중요하지 않습니다. 두 노드가 연결되어 있다는 사실 만 신경 쓰는 것입니다.

Dijkstra의 알고리즘 은 일부 소스 노드에서 시작 하는 최단 경로 트리를 구성 합니다. 최단 경로 트리는 그래프의 모든 노드를 다시 소스 노드에 연결하는 트리이며 소스 노드에서 그래프의 다른 노드까지의 경로 길이가 최소화된다는 속성이 있습니다. 예를 들어 모든 사람이 주요 랜드 마크에 도달 할 수 있도록 최대한 효율적으로 도로 네트워크를 구축하려는 경우 유용합니다. 그러나 최단 경로 트리가 최소 스패닝 트리라는 보장은 없으며 이러한 트리를 구축하는 데 드는 비용은 MST 비용보다 훨씬 클 수 있습니다.

또 다른 중요한 차이점은 알고리즘이 작동하는 그래프 유형에 관한 것입니다. Prim의 알고리즘은 MST의 개념이 그래프가 본질적으로 무 방향이라고 가정하기 때문에 무 방향 그래프에서만 작동합니다. (방향성 그래프에 대해 "최소 스패닝 수목"이라는 것이 있지만이를 찾는 알고리즘은 훨씬 더 복잡합니다.) Dijkstra의 알고리즘은 최단 경로 트리가 실제로 방향을 지정할 수 있기 때문에 방향성 그래프에서 잘 작동합니다. 또한 Dijkstra의 알고리즘 은 음의 에지 가중치를 포함하는 그래프에서 반드시 올바른 솔루션을 산출하지는 않지만 Prim의 알고리즘은이를 처리 할 수 ​​있습니다.

도움이 되었기를 바랍니다!

---

Dijkstra의 알고리즘은 MST를 생성하지 않고 최단 경로를 찾습니다.

이 그래프를 고려하십시오

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

최단 경로는 9이고 MST는 10에서 다른 '경로'입니다.

---

Prim과 Dijkstra 알고리즘은 "relax function"을 제외하고 거의 동일합니다.

Prim에서 :

MST-PRIM (G, w, r) {

        for each key ∈ G.V

            u.key = ∞
            u.parent = NIL

        r.key = 0
        Q = G.V
        while (Q ≠ ø)

            u = Extract-Min(Q)
            for each v ∈ G.Adj[u]

                if (v ∈ Q) and w(u,v) < v.key

                    v.parent = u
                    v.key = w(u,v)    <== relax function, Pay attention here

}

Dijkstra에서 :

Dijkstra (G, w, r) {

        for each key ∈ G.V

            u.key = ∞
            u.parent = NIL

        r.key = 0
        Q = G.V
        while (Q ≠ ø)

            u = Extract-Min(Q)
            for each v ∈ G.Adj[u]

                if (v ∈ Q) and w(u,v) < v.key

                    v.parent = u
                    v.key = w(u,v) + u.key  <== relax function, Pay attention here

}

유일한 차이점은 코드의 마지막 줄인 relax 함수입니다. 최소 스패닝 트리를 검색하는 Prim은 모든 정점을 덮는 전체 가장자리의 최소값 만 고려합니다. 따라서 다음과 같이 보입니다. v.key = w (u, v) 최소 경로 길이를 검색하는 Dijkstra이므로 에지 누적에 관심이 있습니다. 따라서 다음과 같이 보입니다. : v.key = w (u, v) + u.key

---

Dijkstra는 시작 노드와 다른 모든 노드 사이의 최단 경로를 찾습니다. 따라서 그 대가로 시작 노드에서 최소 거리 트리를 얻습니다. 즉, 가능한 한 효율적으로 다른 모든 노드에 도달 할 수 있습니다.

Prims 알고리즘은 주어진 그래프, 즉 모든 비용의 합이 가능한 최소값 인 동안 모든 노드를 연결하는 트리에 대한 MST를 얻습니다.

현실적인 예를 들어 짧은 이야기를 만들려면 :

1. Dijkstra는 이동 시간과 연료를 절약하여 각 목적지까지의 최단 경로를 알고 싶어합니다.
2. Prim은 기차 레일 시스템을 효율적으로 배치하는 방법, 즉 자재 비용을 절약하는 방법을 알고 싶습니다.

---

Dijkstra의 Algorithm의 위키피디아 기사 에서 직접 발췌 :

Dijkstra의 알고리즘의 기초가되는 프로세스는 Prim의 알고리즘에서 사용되는 탐욕스러운 프로세스와 유사합니다. Prim의 목적은 그래프의 모든 노드를 연결하는 최소 스패닝 트리를 찾는 것입니다. Dijkstra는 두 개의 노드에만 관련됩니다. Prim 's는 시작 노드에서 경로의 총 가중치를 평가하지 않고 개별 경로 만 평가합니다.

---

The key difference between the basic algorithms lies in their different edge-selection criteria. Generally, they both use a priority queue for selecting next nodes, but have different criteria to select the adjacent nodes of current processing nodes: Prim's Algorithm requires the next adjacent nodes must be also kept in the queue, while Dijkstra's Algorithm does not:

def dijkstra(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            ...

def prim(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            if v in q and weight(u, v) < v.distance:// <-------selection--------
            ...

The calculations of vertex.distance are the second different point.

---

Dijkstras algorithm is used only to find shortest path.

In Minimum Spanning tree(Prim's or Kruskal's algorithm) you get minimum egdes with minimum edge value.

For example:- Consider a situation where you wan't to create a huge network for which u will be requiring a large number of wires so these counting of wire can be done using Minimum Spanning Tree(Prim's or Kruskal's algorithm) (i.e it will give you minimum number of wires to create huge wired network connection with minimum cost).

Whereas "Dijkstras algorithm" will be used to get the shortest path between two nodes while connecting any nodes with each other.

---

The first distinction is that Dijkstra’s algorithm solves a different problem than Kruskal and Prim. Dijkstra solves the shortest path problem (from a specified node), while Kruskal and Prim finds a minimum-cost spanning tree. The following is a modified form of a description I wrote at this page: Graph algorithms.

For any graph, a spanning tree is a collection of edges sufficient to provide exactly one path between every pair of vertices. This restriction means that there can be no circuits formed by the chosen edges.

A minimum-cost spanning tree is one which has the smallest possible total weight (where weight represents cost or distance). There might be more than one such tree, but Prim and Kruskal are both guaranteed to find one of them.

For a specified vertex (say X), the shortest path tree is a spanning tree such that the path from X to any other vertex is as short as possible (i.e., has the minimum possible weight).

Prim and Dijkstra "grow" the tree out from a starting vertex. In other words, they have a "local" focus; at each step, we only consider those edges adjacent to previously chosen vertices, choosing the cheapest option which satisfies our needs. Meanwhile, Kruskal is a "global" algorithm, meaning that each edge is (greedily) chosen from the entire graph. (Actually, Dijkstra might be viewed as having some global aspect, as noted below.)

To find a minimum-cost spanning tree:

Kruskal (global approach): At each step, choose the cheapest available edge anywhere which does not violate the goal of creating a spanning tree. Prim (local approach): Choose a starting vertex. At each successive step, choose the cheapest available edge attached to any previously chosen vertex which does not violate the goal of creating a spanning tree. To find a shortest-path spanning tree:

Dijkstra: At each step, choose the edge attached to any previously chosen vertex (the local aspect) which makes the total distance from the starting vertex (the global aspect) as small as possible, and does not violate the goal of creating a spanning tree.

Minimum-cost trees and shortest-path trees are easily confused, as are the Prim and Dijkstra algorithms that solve them. Both algorithms "grow out" from the starting vertex, at each step choosing an edge which connects a vertex Y which is in the tree to a vertex Z which is not. However, while Prim chooses the cheapest such edge, Dijkstra chooses the edge which results in the shortest path from X to Z.

A simple illustration is helpful to understand the difference between these algorithms and the trees they produce. In the graph below, starting from the vertex A, both Prim and Dijkstra begin by choosing edge AB, and then adding edge BD. Here is where the two algorithms diverge: Prim completes the tree by adding edge DC, while Dijkstra adds either AC or BC, because paths A-C and A-B-C (both with total distance 30) are shorter than path A-B-D-C (total distance 31).

---

@templatetypedef has covered difference between MST and shortest path. I've covered the algorithm difference in another So answer by demonstrating that both can be implemented using same generic algorithm that takes one more parameter as input: function f(u,v). The difference between Prim and Dijkstra's algorithm is simply which f(u,v) you use.

---

At the code level, the other difference is the API.

You initialize Prim with a source vertex, s, i.e., Prim.new(s); s can be any vertex, and regardless of s, the end result, which are the edges of the minimum spanning tree (MST) are the same. To get the MST edges, we call the method edges().

You initialize Dijkstra with a source vertex, s, i.e., Dijkstra.new(s) that you want to get shortest path/distance to all other vertices. The end results, which are the shortest path/distance from s to all other vertices; are different depending on the s. To get the shortest paths/distances from s to any vertex, v, we call the methods distanceTo(v) and pathTo(v) respectively.

참고URL : https://stackoverflow.com/questions/14144279/difference-between-prims-and-dijkstras-algorithms