이 글에서는 C++을 사용하여 Set(집합)을 활용한 다익스트라(Dijkstra) 알고리즘을 구현하는 방법을 알아봅니다. 다익스트라 알고리즘은 주어진 시작 정점을 루트로 하는 최단 경로 트리(shortest path tree)를 생성하는 대표적인 최단 경로 알고리즘입니다.
구현 과정에서는 두 개의 집합이 필요합니다. 하나는 최단 경로 트리에 이미 포함된 정점들을 관리하는 집합이고, 다른 하나는 아직 최단 경로 트리에 포함되지 않은 정점들을 관리하는 집합입니다. 매 단계마다 아직 포함되지 않은 집합에서 시작 정점으로부터의 거리가 가장 짧은 정점을 찾아 선택하는 방식으로 동작합니다.
알고리즘 동작 원리
다익스트라 알고리즘은 다음과 같은 순서로 최소 거리를 계산합니다.
시작
최소 거리를 찾기 위한 dijkstra() 함수:
1) 최단 경로 트리에 포함된 정점을 추적하는 집합(Set)을 생성한다.
초기에는 이 집합이 비어 있다.
2) 입력 그래프의 모든 정점에 거리 값을 할당한다.
모든 거리 값을 무한대(INFINITE)로 초기화하고,
시작 정점의 거리 값만 0으로 설정하여 가장 먼저 선택되도록 한다.
3) 집합이 모든 정점을 포함할 때까지 반복한다.
a) 집합에 없으면서 거리 값이 최소인 정점 u를 선택한다.
b) 정점 u를 집합에 추가한다.
c) u에 인접한 모든 정점의 거리 값을 갱신한다.
거리 값 갱신 시에는 모든 인접 정점을 순회하며,
인접 정점 v에 대해 (u까지의 거리 값 + 간선 u-v의 가중치)가
v의 현재 거리 값보다 작으면 v의 거리 값을 갱신한다.
끝예제 코드
아래는 위 알고리즘을 C++로 구현한 전체 예제 코드입니다.
#include <iostream>
#include <climits>
#include <set>
using namespace std;
#define N 5
int minDist(int dist[], bool Set[]) // 최소 거리 계산
{
int min = INT_MAX, min_index;
for (int v = 0; v < N; v++)
if (Set[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
int printSol(int dist[], int n) // 결과 출력
{
cout<<"Vertex Distance from Source\n";
for (int i = 0; i < N; i++)
cout<<" \t \n"<< i<<" \t "<<dist[i];
}
void dijkstra(int g[N][N], int src)
{
int dist[N];
bool Set[N];
for (int i = 0; i < N; i++)
dist[i] = INT_MAX, Set[i] = false;
dist[src] = 0;
for (int c = 0; c < N- 1; c++)
{
int u = minDist(dist, Set);
Set[u] = true;
for (int v = 0; v < N; v++)
if (!Set[v] && g[u][v] && dist[u] != INT_MAX && dist[u]
+ g[u][v] < dist[v])
dist[v] = dist[u] + g[u][v];
}
printSol(dist, N);
}
int main()
{
int g[N][N] = { { 0, 4, 0, 0, 0 },
{ 4, 0, 7, 0, 0 },
{ 0, 8, 0, 9, 0 },
{ 0, 0, 7, 0, 6 },
{ 0, 2, 0, 9, 0 }};
dijkstra(g, 0);
return 0;
}실행 결과
위 코드를 컴파일하여 실행하면, 시작 정점(0번 정점)으로부터 각 정점까지의 최단 거리가 다음과 같이 출력됩니다.
Vertex Distance from Source 0 0 1 4 2 11 3 20 4 26
코드 설명
minDist() 함수는 아직 최단 경로 트리에 포함되지 않은 정점 중에서 거리 값이 가장 작은 정점의 인덱스를 반환합니다. dijkstra() 함수는 모든 정점의 거리 값을 무한대(INT_MAX)로 초기화한 뒤, 시작 정점의 거리만 0으로 설정합니다. 이후 (정점 개수 - 1)번 반복하면서 최소 거리 정점을 선택하고, 해당 정점을 집합에 추가한 다음 인접 정점들의 거리 값을 갱신합니다. 간선이 존재하지 않는 경우 가중치가 0이므로, g[u][v]가 0이 아닌 경우에만 갱신을 수행합니다.
이 알고리즘의 시간 복잡도는 인접 행렬을 사용하는 경우 O(V²)이며, 우선순위 큐나 이진 힙을 함께 사용하면 O((V + E) log V)까지 개선할 수 있습니다. 단, 다익스트라 알고리즘은 간선의 가중치가 음수인 그래프에서는 올바른 결과를 보장하지 않으므로, 음수 가중치가 존재하는 경우에는 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 합니다.