[그래프] 다익스트라 / Dijkstra's algorithm
2024. 10. 3. 07:42ㆍ🐣/Algorithm
다익스트라 알고리즘 / Dijkstra's algorithm
다익스트라 알고리즘은 단일 출발점 최단 경로를 찾는 알고리즘입니다. 가중치가 음수가 아닌 그래프에서 출발점에서 모든 다른 정점까지의 최단 경로를 구할 때 사용됩니다. 다익스트라 알고리즘은 우선순위 큐(Priority Queue)를 이용해 최단 거리가 가장 작은 정점을 빠르게 탐색하여 최적화된 성능을 제공합니다.
다익스트라 알고리즘의 특징
- 음의 가중치 간선 허용 안 함: 음의 가중치가 있는 그래프에서는 올바르게 작동하지 않습니다.
- 우선순위 큐 사용: 최단 경로를 더 효율적으로 찾기 위해, 가중치가 가장 작은 정점을 빠르게 선택하기 위해 우선순위 큐(최소 힙)을 사용합니다.
- 시간 복잡도: O((V + E) * log V) - 여기서 V는 정점의 수, E는 간선의 수입니다. 우선순위 큐를 사용하는 경우, 힙 연산이 log V 시간에 수행되기 때문에 매우 효율적입니다.
다익스트라 알고리즘의 동작 원리
- 초기화: 출발 정점의 거리를 0으로 설정하고, 나머지 정점들의 거리는 무한대로 초기화합니다.
- 우선순위 큐 사용: 거리가 최소인 정점을 큐에서 꺼내고, 이 정점과 연결된 모든 간선을 탐색하여 인접한 정점의 최단 거리를 업데이트합니다.
- 반복: 모든 정점에 대해 위의 과정을 반복합니다. 정점의 최단 거리가 갱신될 때마다 우선순위 큐에 삽입하여 다음으로 최단 거리가 작은 정점을 선택합니다.
다익스트라 알고리즘의 C++ 구현
아래는 C++에서 우선순위 큐를 사용하여 다익스트라 알고리즘을 구현한 코드입니다. 이 코드는 특정 출발지에서 모든 다른 정점까지의 최단 거리를 구하는 방식으로 동작합니다.
코드예시 BOJ 18352 특정 거리의 도시 찾기
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9; // 무한대 값 (충분히 큰 값)
vector<int> dijkstra(int n, int start, vector<vector<pair<int, int>>>& graph) {
vector<int> distance(n + 1, INF); // 최단 거리 배열 초기화
distance[start] = 0;
// 우선순위 큐 선언 (pair<int, int>: (거리, 정점))
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start}); // (거리, 정점) 순서로 삽입
while (!pq.empty()) {
int currentDist = pq.top().first;
int currentNode = pq.top().second;
pq.pop();
// 현재 노드의 최단 거리가 이미 처리된 거리보다 크다면 무시
if (currentDist > distance[currentNode]) {
continue;
}
// 현재 노드에 연결된 다른 노드들을 확인
for (auto& edge : graph[currentNode]) {
int nextNode = edge.first;
int weight = edge.second;
int newDist = currentDist + weight;
// 더 짧은 경로를 발견한 경우 업데이트
if (newDist < distance[nextNode]) {
distance[nextNode] = newDist;
pq.push({newDist, nextNode});
}
}
}
return distance;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k, x;
cin >> n >> m >> k >> x;
// 인접 리스트로 그래프 표현 (pair<int, int>: (도착 노드, 가중치))
vector<vector<pair<int, int>>> graph(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back({b, 1}); // 모든 간선의 가중치는 1로 설정
}
// 다익스트라 알고리즘 실행
vector<int> distance = dijkstra(n, x, graph);
// 최단 거리가 정확히 k인 도시 찾기
vector<int> result;
for (int i = 1; i <= n; i++) {
if (distance[i] == k) {
result.push_back(i);
}
}
// 결과 출력
if (result.empty()) {
cout << "-1\n";
} else {
sort(result.begin(), result.end());
for (int city : result) {
cout << city << "\n";
}
}
return 0;
}
코드 설명
- 그래프 표현:
- 그래프는 인접 리스트 형태로 표현됩니다. graph[i]는 정점 i와 연결된 모든 간선을 (도착 정점, 가중치) 형태로 저장합니다.
- 입력을 받아서 간선을 추가할 때, 모든 간선의 가중치를 1로 설정했습니다 (graph[a].push_back({b, 1})).
- 다익스트라 알고리즘 (dijkstra 함수):
- 최단 거리 배열: distance 배열은 출발점에서 각 정점까지의 최단 거리를 저장합니다. 모든 값을 초기화한 후 출발점의 거리를 0으로 설정합니다.
- 우선순위 큐 사용: 최소 힙을 사용하기 위해 priority_queue를 사용하며, greater<pair<int, int>>를 지정하여 최소 거리가 먼저 나오는 우선순위 큐를 만듭니다.
- 정점 처리: 큐에서 거리가 가장 짧은 정점을 꺼내고, 그 정점과 연결된 간선을 따라 다른 정점의 최단 거리를 갱신합니다. 최단 거리가 갱신될 때마다 큐에 새로 넣습니다.
- 결과 출력:
- 최단 거리가 K인 도시들을 result 벡터에 모아 오름차순으로 출력합니다.
- 결과가 없을 경우 -1을 출력합니다.
다익스트라 알고리즘의 시간 복잡도
- 시간 복잡도: O((V + E) * log V).
- V는 정점의 수 (n), E는 간선의 수 (m)입니다.
- log V는 우선순위 큐(힙)에서 삽입하거나 삭제할 때 소요되는 시간입니다.
- 따라서, 그래프의 모든 정점과 간선을 탐색하며 우선순위 큐에서 정점 선택을 효율적으로 하기 위해 로그 시간이 더해집니다.
다익스트라 알고리즘과 BFS의 차이점
- 가중치:
- BFS는 모든 간선의 가중치가 같을 때(예: 모든 간선의 가중치가 1인 경우) 효율적으로 사용할 수 있습니다.
- 다익스트라 알고리즘은 가중치가 다를 때, 최단 거리를 찾기 위해 사용합니다.
- 우선순위 큐 사용:
- 다익스트라는 우선순위 큐를 사용하여 현재 방문 가능한 정점 중 가장 비용이 적은 정점을 먼저 탐색합니다.
- BFS는 큐를 사용하여 정점들을 동일한 거리 순서로 탐색합니다.
결론
- 다익스트라 알고리즘은 가중치가 양수일 때 최단 거리를 찾는 데 매우 효율적입니다.
- 이 알고리즘은 최소 힙을 이용해 정점 선택을 최적화하여 시간 복잡도를 줄입니다.
- 이 문제에서 BFS도 적합하지만, 다익스트라 알고리즘을 사용하면 더 범용적이고 복잡한 문제(예: 가중치가 다양한 경우)에도 적용할 수 있습니다.
다익스트라 문제 추천
'🐣 > Algorithm' 카테고리의 다른 글
[그래프/정렬/유향] 위상정렬 / Topological Sorting (0) | 2024.10.20 |
---|---|
[누적합] 세그먼트트리 / Segment tree (0) | 2024.10.02 |
[그래프] 벨만-포드 / Bellman–Ford algorithm (2) | 2024.10.01 |
[Swift] 순열 / permutation / 조합 / combination (0) | 2024.04.21 |
[DP] 타뷸레이션 (0) | 2024.03.21 |