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



Answers

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

이 그래프를 고려해보십시오.

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

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

Question

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




Dijkstras 알고리즘 은 최단 경로 찾기에만 사용됩니다.

최소 스패닝 트리 (Prim 또는 Kruskal 알고리즘) 에서 최소 에지 값을 갖는 최소 egdes를 얻습니다.

예를 들면 : - 많은 수의 전선을 필요로하는 커다란 네트워크를 만들지 않고 최소 스패닝 트리 (Prim 또는 Kruskal의 알고리즘)를 사용하여 배선을 계산할 수있는 상황을 고려하십시오 (예 : 최소한의 비용으로 거대한 유선 네트워크 연결을 생성하기위한 최소 수의 전선을 제공하십시오).

반면에 "Dijkstras 알고리즘" 은 두 노드 사이의 최단 경로를 얻는 데 사용되며 다른 노드는 서로 연결합니다.




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

Prims 알고리즘은 주어진 그래프, 즉 모든 노드를 연결하는 트리에 대해 MST를 가져오고 모든 비용의 합은 가능한 한 최소입니다.

현실적인 예를 통해 짧은 이야기를 만들려면 다음과 같이하십시오.

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



기본 알고리즘 간의 주요 차이점은 서로 다른 에지 선택 기준에 있습니다. 일반적으로 이들은 다음 노드를 선택하기 위해 우선 순위 대기열을 사용하지만 현재 처리 노드의 인접 노드를 선택하는 데는 다른 기준을 갖습니다. Prim 's Algorithm은 Dijkstra 's Algorithm이 다음과 같은 인접 노드를 큐에 보관해야합니다.

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--------
            ...

vertex.distance 의 계산은 두 번째 다른 점입니다.




코드 수준에서 다른 차이점은 API입니다.

소스 버텍스, 즉 Prim.new(s) Prim을 초기화합니다. s 는 임의의 정점이 될 수 있고 s에 관계없이 최소 스패닝 트리 (MST)의 가장자리 인 최종 결과는 동일합니다. MST 가장자리를 얻으려면 edges() 메서드를 호출합니다.

Dijkstra를 소스 버텍스, 즉 Dijkstra.new(s) 모든 다른 버텍스에 대한 최단 경로 / 거리를 얻기를 원함 Dijkstra.new(s) 초기화합니다. 최종 결과는 s 에서 다른 모든 정점까지 최단 거리 / 거리입니다. s 에 따라 다릅니다. s 에서 임의의 정점 v 까지 최단 경로 / 거리를 얻으려면 distanceTo(v)pathTo(v) 메서드를 각각 호출합니다.




Related