[Algorithm] 다익스트라 알고리즘 (Dijkstra Algorithm)쉽게 배우기 (C++ 코드 예제 포함)
다익스트라 알고리즘(Dijkstra Algorithm)
다익스트라 알고리즘은 그래프의 한 시작 정점(source vertex)에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다.
각 정점까지의 최단 거리를 저장하면서, 아직 방문하지 않은 정점 중 현재까지 계산된 최단 거리가 가장 짧은 정점을 선택하여 탐색을 진행합니다.
(출처 : https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/)
특징
- 그리디 알고리즘(Greedy Algorithm): 각 단계에서 현재까지 발견된 최단 거리를 기준으로 가장 가까운 정점을 선택합니다.
- 음수 가중치 간선이 없어야 함: 음수 가중치가 있는 경우 최단 경로를 제대로 찾지 못할 수 있습니다. (음수 가중치가 있는 경우에는 벨만-포드 알고리즘을 사용해야 합니다.)
- 우선순위 큐(Priority Queue) 활용: 효율적인 최단 거리 정점 선택을 위해 우선순위 큐를 사용합니다.
동작방식
- 시작 정점의 거리를 0으로 설정하고, 다른 모든 정점의 거리를 무한대(∞)로 초기화합니다.
- 모든 정점을 “방문하지 않음”으로 표시합니다.
- 아직 방문하지 않은 정점 중에서 현재까지 계산된 거리가 가장 짧은 정점을 선택합니다 (우선순위 큐 활용).
- 선택한 정점을 “방문함”으로 표시합니다.
- 선택한 정점에 인접한 모든 정점에 대해, 현재까지 계산된 거리보다 선택한 정점을 거쳐 가는 거리가 더 짧다면, 해당 정점의 거리를 갱신합니다.
- 모든 정점을 방문할 때까지 3~5단계를 반복합니다.
벨만-포드 알고리즘과의 비교
다익스트라 알고리즘과 함께 최단 경로를 찾는 대표적인 알고리즘으로 벨만-포드 알고리즘(Bellman-Ford Algorithm)이 있습니다.
- 다익스트라 알고리즘: 음수 가중치 간선이 없어야 함, 우선순위 큐 사용, 일반적으로 더 빠름
- 벨만-포드 알고리즘: 음수 가중치 간선이 있어도 동작 가능, 음수 사이클 감지 가능
음수 가중치가 없는 그래프에서는 다익스트라 알고리즘이 효율적이고, 음수 가중치가 있는 그래프에서는 벨만-포드 알고리즘을 사용해야 합니다.
시간 복잡도
- 우선순위 큐를 사용하는 경우: O(E log V) (E는 간선의 개수, V는 정점의 개수)
- 모든 간선을 탐색하는 경우: O(V^2) (인접 행렬 사용 시)
활용 예시
- 네비게이션 시스템: 지도에서 최단 경로 찾기
- 네트워크 라우팅: 네트워크에서 데이터 패킷의 최적 경로 찾기
- GPS 네비게이션
- 통신 네트워크
- 게임 AI: 게임 캐릭터의 최적 이동 경로 계산
장단점
장점
구현이 비교적 간단하고 효율적입니다.다른 최단 경로 알고리즘에 비해 구현이 직관적이고 코드가 간결한 편입니다. 특히 우선순위 큐를 사용하면 효율적인 시간 복잡도를 보장합니다.하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구할 수 있습니다.특정 지점에서 다른 모든 지점까지의 최단 거리를 한 번의 실행으로 계산할 수 있어 매우 유용합니다.다양한 자료 구조로 구현 가능합니다.인접 행렬, 인접 리스트, 우선순위 큐 등 다양한 자료 구조를 사용하여 구현할 수 있으며, 그래프의 특성에 따라 적절한 자료 구조를 선택하여 성능을 최적화할 수 있습니다.경로 추적이 용이합니다.단순히 최단 거리뿐만 아니라, 최단 경로를 구성하는 정점들의 순서를 추적하도록 알고리즘을 쉽게 수정할 수 있습니다. 이를 통해 실제 경로를 복원할 수 있습니다.
단점
음수 가중치를 가진 간선이 있는 그래프에서는 사용할 수 없습니다.다익스트라 알고리즘은 탐욕적인 방식으로 동작하기 때문에, 음수 가중치가 있는 경우 최단 경로를 제대로 찾지 못합니다. 음수 가중치가 있는 경우에는 벨만-포드 알고리즘(Bellman-Ford Algorithm)과 같은 다른 알고리즘을 사용해야 합니다. 이것이 다익스트라 알고리즘의 가장 큰 제약 조건입니다.간선이 많은 큰 그래프의 경우 성능이 저하될 수 있습니다.특히 우선순위 큐를 사용하는 경우에도, 간선의 수가 매우 많아지면 큐 연산에 소요되는 시간이 증가하여 성능이 저하될 수 있습니다.메모리 사용량이 클 수 있습니다.그래프의 크기가 크거나 간선이 많을 경우, 그래프 자체를 저장하기 위한 메모리뿐만 아니라, 거리 정보를 저장하기 위한 추가적인 메모리도 필요하기 때문에 메모리 사용량이 증가할 수 있습니다.동일한 거리에 여러 경로가 있는 경우 최적의 경로를 보장하지 않습니다.즉, 여러 개의 최단 경로가 존재할 경우, 그 중 하나의 경로만 찾게 됩니다. 특정 조건에 맞는 최적의 경로 (예: 경유지 수가 가장 적은 경로) 를 찾아야 하는 경우에는 적합하지 않을 수 있습니다.지형이나 교통 상황과 같은 다른 요소는 고려하지 않습니다.기본적인 다익스트라 알고리즘은 간선의 가중치만을 고려하여 최단 경로를 계산합니다. 실제 도로망이나 네트워크에서는 지형, 교통 상황, 통행료 등 다양한 요소가 경로 선택에 영향을 미치므로, 이러한 요소를 고려하기 위해서는 알고리즘을 변형하거나 추가적인 처리가 필요합니다.
예제
[인접 리스트, 우선순위 큐 사용]
#include <iostream>
#include <vector>
#include <queue>
#include <limits> // numeric_limits 사용을 위해 포함
using namespace std;
const int INF = numeric_limits<int>::max(); // 무한대 값
struct Edge {
int to, weight;
};
int main() {
int numVertices = 6;
vector<vector<Edge>> adj(numVertices);
// 간선 추가 (예시)
adj[0].push_back({1, 4});
adj[0].push_back({2, 2});
adj[1].push_back({2, 1});
adj[1].push_back({3, 5});
adj[2].push_back({3, 8});
adj[2].push_back({4, 10});
adj[3].push_back({4, 2});
adj[3].push_back({5, 6});
adj[4].push_back({5, 3});
int startVertex = 0; // 시작 정점
vector<int> dist(numVertices, INF); // 최단 거리를 저장하는 벡터
dist[startVertex] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 우선순위 큐 (거리, 정점)
pq.push({0, startVertex});
while (!pq.empty()) {
int currentDist = pq.top().first;
int currentVertex = pq.top().second;
pq.pop();
if (currentDist > dist[currentVertex]) { // 이미 더 짧은 경로를 찾은 경우
continue;
}
for (const auto& edge : adj[currentVertex]) {
int nextVertex = edge.to;
int nextDist = currentDist + edge.weight;
if (nextDist < dist[nextVertex]) { // 더 짧은 경로를 찾은 경우
dist[nextVertex] = nextDist;
pq.push({nextDist, nextVertex});
}
}
}
cout << "Shortest distances from vertex " << startVertex << ":" << endl;
for (int i = 0; i < numVertices; i++) {
cout << "To vertex " << i << ": " << dist[i] << endl;
}
return 0;
}
[인접 행렬과 배열만을 사용]
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
int main() {
int numVertices = 6;
vector<vector<int>> adjMatrix(numVertices, vector<int>(numVertices, INF)); // 인접 행렬
// 자기 자신으로 가는 비용은 0으로 초기화
for (int i = 0; i < numVertices; ++i) {
adjMatrix[i][i] = 0;
}
// 간선 추가 (예시)
adjMatrix[0][1] = 4;
adjMatrix[0][2] = 2;
adjMatrix[1][2] = 1;
adjMatrix[1][3] = 5;
adjMatrix[2][3] = 8;
adjMatrix[2][4] = 10;
adjMatrix[3][4] = 2;
adjMatrix[3][5] = 6;
adjMatrix[4][5] = 3;
int startVertex = 0;
vector<int> dist(numVertices, INF);
dist[startVertex] = 0;
vector<bool> visited(numVertices, false);
for (int count = 0; count < numVertices - 1; count++) { // 모든 정점에 대해 반복
int minDist = INF;
int minVertex = -1;
// 아직 방문하지 않은 정점 중 최소 거리를 가진 정점 찾기
for (int v = 0; v < numVertices; v++) {
if (!visited[v] && dist[v] <= minDist) {
minDist = dist[v];
minVertex = v;
}
}
if (minVertex == -1) break; // 더 이상 연결된 정점이 없는 경우
visited[minVertex] = true;
// 선택된 정점을 거쳐서 가는 경로를 통해 거리 갱신
for (int v = 0; v < numVertices; v++) {
if (!visited[v] && adjMatrix[minVertex][v] != INF &&
dist[minVertex] != INF &&
dist[minVertex] + adjMatrix[minVertex][v] < dist[v]) {
dist[v] = dist[minVertex] + adjMatrix[minVertex][v];
}
}
}
cout << "Shortest distances from vertex " << startVertex << ":" << endl;
for (int i = 0; i < numVertices; i++) {
cout << "To vertex " << i << ": " << dist[i] << endl;
}
return 0;
}