MST(크루스칼, 프림)와 최단경로(다익스트라)가 헷갈려서 작성하게 됨
MST(최소 신장 트리) 알고리즘과 최단 경로 알고리즘의 주요 차이점은 목적과 적용되는 그래프의 속성입니다.
각각의 알고리즘은 특정 문제 상황에 맞춰서 사용됩니다.
1. MST (크루스칼, 프림 알고리즘)
목적: MST 알고리즘은 그래프에서 모든 노드를 연결하되, 간선의 가중치 합이 최소가 되도록 하는 트리를 찾는 것입니다. 즉, 그래프 내의 모든 노드를 포함하면서 최소 비용으로 연결된 경로를 구하는 데 사용됩니다.
- 적용 가능 그래프: MST는 연결된 무방향 가중치 그래프에서 사용됩니다.
알고리즘:
- 크루스칼 알고리즘: 간선 중심으로 최소 가중치를 가지는 간선을 선택해 나가면서 트리를 확장하는 방식으로, 간선을 정렬한 후, 사이클을 형성하지 않는 간선들을 선택합니다.
- 프림 알고리즘: 정점 중심으로, 한 정점에서 시작하여 점차 인접한 정점을 최소 비용으로 연결해 나가면서 트리를 확장합니다.
2. 최단 경로 (다익스트라 알고리즘)
목적: 최단 경로 알고리즘은 특정 출발 노드에서 목표 노드까지의 경로 가중치 합이 최소가 되는 경로를 찾는 것입니다. 모든 노드가 아닌, 한 노드에서 다른 노드까지의 최소 비용 경로가 필요할 때 사용합니다.
- 적용 가능 그래프: 다익스트라 알고리즘은 방향성 또는 무방향성 가중치 그래프에서 사용 가능하며, 음수 가중치가 없는 경우에 적합합니다.
알고리즘:
- 다익스트라 알고리즘: 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하며, 가중치가 낮은 정점을 먼저 처리하는 우선순위 큐(힙)를 사용하여 효율성을 높입니다.
핵심 차이점 요약
| 알고리즘 | 목적 | 적용 그래프 | 특징 |
|---|---|---|---|
| MST | 모든 노드를 최소 비용으로 연결 | 무방향 가중치 그래프 | 전체 트리 구성 |
| 최단 경로 | 특정 노드에서 목표 노드까지의 최소 비용 경로 | 방향성/무방향성 가중치 그래프 | 출발지-목표지 간 최단 경로 |
결국 MST는 그래프를 전체적으로 연결할 때 유용하고, 최단 경로 알고리즘은 특정 경로 비용을 구할 때 사용하는 차이가 있습니다.
