[algorithm] 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”을 제외하고 거의 동일합니다.
꼼꼼한:
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)
alt = w(u,v) <== relax function, Pay attention here
if alt < v.key
v.parent = u
v.key = alt
}
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)
alt = w(u,v) + u.key <== relax function, Pay attention here
if alt < v.key
v.parent = u
v.key = alt
}
유일한 차이점은 릴랙스 기능인 화살표로 표시됩니다.
- 최소 스패닝 트리를 검색하는 Prim은 모든 정점을 덮는 전체 가장자리의 최소값 만 고려합니다. 릴렉스 기능은
alt = w(u,v) - 최소 경로 길이를 검색하는 Dijkstra는 에지 누적을 고려합니다. 릴렉스 기능은
alt = w(u,v) + u.key
답변
Dijsktra의 알고리즘은 노드 i에서 모든 노드까지 의 최소 거리 를 찾습니다 (i 지정). 따라서 그 대가로 노드 i에서 최소 거리 트리를 얻습니다.
Prims 알고리즘은 주어진 그래프에 대한 최소 스패닝 트리 를 가져옵니다 . 모든 비용의 합계가 가능한 최소 인 동안 모든 노드를 연결하는 트리입니다.
따라서 Dijkstra 를 사용하면 선택한 노드에서 최소 비용으로 다른 노드로 이동할 수 있습니다. Prim ‘s에서는이를 얻을 수 없습니다.
답변
내가 보는 유일한 차이점은 Prim의 알고리즘은 최소 비용 에지를 저장하는 반면 Dijkstra의 알고리즘은 소스 버텍스에서 현재 버텍스까지의 총 비용을 저장한다는 것입니다.
Dijkstra는 비용이 최소가되도록 소스 노드에서 대상 노드로가는 길을 제공합니다. 그러나 Prim의 알고리즘은 모든 노드가 연결되고 총 비용이 최소가되도록 최소 스패닝 트리를 제공합니다.
간단히 말해서 :
따라서 여러 도시를 연결하기 위해 기차를 배치하려면 Prim의 algo를 사용합니다. 그러나 가능한 한 많은 시간을 절약하면서 한 도시에서 다른 도시로 이동하려면 Dijkstra의 algo를 사용합니다.
답변
둘 다 다음과 같이 정확히 동일한 일반 알고리즘을 사용하여 구현할 수 있습니다.
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의 경우 통과 f = w(u, v)하고 Dijkstra의 경우 통과 f = u.key + w(u, v)합니다.
또 다른 흥미로운 점은 위의 Generic도 BFS (Breadth First Search)를 구현할 수 있다는 것입니다. 값 비싼 우선 순위 대기열이 실제로 필요하지 않기 때문에 과도 할 수 있습니다. 일반 알고리즘을 BFS로 전환하려면 f = u.key + 1모든 가중치를 1로 적용하는 것과 동일한 방식을 전달합니다 (즉, BFS는 지점 A에서 B로 이동하는 데 필요한 최소 가장자리 수를 제공합니다).
직관
위의 일반적인 알고리즘에 대해 생각하는 좋은 방법은 다음과 같습니다. 두 개의 버킷 A와 B로 시작합니다. 처음에는 버킷 A가 비어 있도록 모든 정점을 B에 넣습니다. 그런 다음 하나의 정점을 B에서 A로 이동합니다. 이제 A의 정점에서 B의 정점까지 교차하는 모든 가장자리를 살펴 봅니다. 이러한 교차 가장자리의 일부 기준을 사용하여 하나의 가장자리를 선택하고 해당 정점을 B에서 A. B가 비워 질 때까지이 과정을 반복합니다.
이 아이디어를 구현하는 무차별 대입 방법은 B로 넘어가는 A의 정점에 대한 가장자리의 우선 순위 대기열을 유지하는 것입니다. 그래프가 희박하지 않으면 문제가 될 것입니다. 그래서 질문은 대신 정점의 우선 순위 대기열을 유지할 수 있습니까? 실제로 이것은 우리의 결정에 따라 B에서 선택할 정점입니다.
역사적 맥락
두 알고리즘이면의 기술의 일반 버전이 개념적으로 전자 컴퓨터가 없었을 때도 1930 년만큼 오래되었다는 것은 흥미 롭습니다.
이야기는 최소 비용의 전기선으로 Moravia (현재 체코 공화국)의 도시를 연결하는 방법을 알아 내려는 가족 친구를위한 알고리즘이 필요한 Otakar Borůvka로 시작됩니다. 그는 컴퓨터 과학이 존재하지 않았기 때문에 1926 년에 수학 관련 저널에 자신의 알고리즘을 발표했습니다. 이것은 Borůvka 알고리즘의 개선을 생각하고 1930 년에 발표 한 Vojtěch Jarník의 관심을 끌었습니다. 그는 실제로 우리가 지금 알고있는 것과 동일한 알고리즘을 발견하여 1957 년에 다시 발견 한 Prim의 알고리즘을 발견했습니다.
이 모든 것들과는 별개로, 1956 년 Dijkstra는 그의 연구소가 개발 한 새로운 컴퓨터의 기능을 보여주는 프로그램을 작성해야했습니다. 그는 컴퓨터가 네덜란드의 두 도시 사이를 여행 할 연결을 찾는 것이 멋질 것이라고 생각했습니다. 그는 20 분 만에 알고리즘을 설계했습니다. 그는 (그의 컴퓨터가 6 비트이기 때문에) 약간 단순화 된 64 개 도시의 그래프를 만들고이 1956 년 컴퓨터 용 코드를 작성했습니다. 그러나 그는 주로 컴퓨터 과학 저널이 없었고 이것이 그다지 중요하지 않을 것이라고 생각했기 때문에 알고리즘을 발표하지 않았습니다. 다음 해에 그는 전선 길이를 최소화하기 위해 새 컴퓨터의 터미널을 연결하는 문제에 대해 배웠습니다. 그는이 문제에 대해 생각하고 Jarník / Prim ‘을 재발견했습니다. 그가 1 년 전에 발견 한 최단 경로 알고리즘과 동일한 기술을 다시 사용하는 s 알고리즘. 그그의 알고리즘은 모두 펜이나 종이를 사용하지 않고 설계되었다고 언급 했습니다. 1959 년에 그는 2 페이지 반에 불과한 논문에 두 알고리즘을 모두 발표했습니다 .
답변
Dijkstra는 시작 노드와 다른 모든 노드 사이의 최단 경로를 찾습니다. 따라서 그 대가로 시작 노드에서 최소 거리 트리를 얻습니다. 즉, 가능한 한 효율적으로 다른 모든 노드에 도달 할 수 있습니다.
Prims 알고리즘은 주어진 그래프, 즉 모든 비용의 합계가 가능한 최소값 인 동안 모든 노드를 연결하는 트리에 대한 MST를 얻습니다.
현실적인 예를 들어 짧은 이야기를 만들려면 :
- Dijkstra는 이동 시간과 연료를 절약하여 각 목적지까지의 최단 경로를 알고 싶어합니다.
- Prim은 기차 레일 시스템을 효율적으로 배치하는 방법, 즉 자재 비용을 절약하는 방법을 알고 싶어합니다.
