다익스트라 vs 프림

 

다익스트라 알고리즘과 프림 알고리즘에 대한 차이가 궁금해져 찾아봤다.

 

다익스트라와 프림은 모두 그래프 알고리즘 중 하나로, 그래프에서 최소 비용의 경로 또는 트리를 찾는 데 사용된다. 그러나 두 알고리즘은 목적과 적용되는 상황에서 차이가 있다.

 

1. 목적

- 다익스트라 알고리즘 : 주어진 출발 노드에서 다른 모든 노드까지의 최단 경로를 찾는 것이 목적이다. 주로 하나의 출발점에서 다른 모든 지점까지의 최단 경로를 찾는 데 사용된다.

- 프림 알고리즘 : 주어진 그래프에서 최소 신장 트리를 찾는 것이 목적이다. 주로 그래프에서 모든 노드를 연결하는 최소 비용의 트리를 찾는 데 사용된다.

최소 신장 트리

 

그래프에서 모든 노드를 가장 적은 비용으로 연결하는 트리.

그래프의 모든 노드를 포함하고, 사이클이 없어야 한다. 

 

최소 신장 트리의 대표적인 알고리즘 : 프림 알고리즘, 크루스칼 알고리즘

- 프림 알고리즘 :  하나의 노드를 시작으로 하여 연결되지 않은 노드들 중에서 최소 가중치 간선을 선택하여 트리를 확장해가는 방식이다.

- 크루스칼 알고리즘 : 모든 간선을 가중치 순으로 정렬한 뒤, 가장 가중치가 작은 간선부터 선택하여 사이클을 형성하지 않는 경우에만 트리에 추가하는 방식이다.

 

2. 적용

- 다익스트라 알고리즘 :  가중치가 음이 아닌 그래프에서 사용된다. 음의 가중치가 있는 경우에는 정확한 결과를 보장할 수 없다.

- 프림 알고리즘 : 가중치가 음이 아닌 그래프에서도 사용할 수 있지만, 주로 가중치가 양수인 경우에 사용된다.

 

3.동작

- 다익스트라 알고리즘 : 시작 노드로부터 각 노드까지의 최단 거리를 차례로 구해가면서, 최소 힙을 사용하여 탐색하는 방식이다.

- 프림 알고리즘 : 시작 노드부터 출발하여 각 단계에서 연결되지 않은 노드 중 가장 가까운 노드를 추가해가면서, 최소 신장 트리를 구축해나가는 방식이다.

 

4. 구성

- 다익스트라 알고리즘 : 최소 힙을 사용하여 각 노드까지의 최단 거리를 계산하고 업데이트한다.

- 프림 알고리즘 : 최소 힙을 사용하여 현재 트리와 연결되지 않은 노드 간의 최소 가중치 간선을 선택하여 트리를 확장한다.

 

-> 다익스트라 알고리즘은 최단 경로 문제를 해결하는 데 사용되고, 프림 알고리즘은 최소 신장 트리를 찾는 데 사용된다.