다익스트라 알고리즘이란?
다익스트라 알고리즘은 가중치 그래프에서 시작 정점(source)으로부터 다른 모든 정점까지의 최단 거리를 구하는 대표적인 탐욕(greedy) 기반 알고리즘입니다. 이번 글에서 다룰 문제는 앞선 예제와 본질적으로 동일하지만, 한 가지 중요한 차이점이 있습니다. 바로 그래프를 인접 행렬(adjacency matrix) 형태로 표현한다는 점입니다.
최단 경로 계산의 관점에서 보면 비용 행렬(cost matrix)과 인접 행렬은 사실상 같은 역할을 하므로, 두 용어를 혼용해도 무방합니다. 인접 행렬을 사용하는 이 구현 방식의 시간 복잡도는 O(V²)이며, 여기서 V는 그래프 G(V, E)의 정점 개수입니다.
입력 및 출력
입력:
인접 행렬:
출력:
0 to 1, Using: 0, Cost: 3
0 to 2, Using: 1, Cost: 5
0 to 3, Using: 1, Cost: 4
0 to 4, Using: 3, Cost: 6
0 to 5, Using: 2, Cost: 7
0 to 6, Using: 4, Cost: 7
출력 결과를 해석하면 다음과 같습니다. 예를 들어 "0 to 6, Using: 4, Cost: 7"은 정점 0에서 정점 6으로 갈 때 직전에 정점 4를 거치며, 총 비용이 7이라는 의미입니다.
알고리즘 동작 원리
다익스트라 알고리즘은 매 단계마다 아직 확정되지 않은 정점 중 시작점으로부터의 거리가 가장 짧은 정점을 하나씩 선택하여 '확정' 상태로 만듭니다. 그런 다음 해당 정점을 경유할 때 더 짧은 경로가 발견되는 인접 정점들의 거리 값을 갱신(dist relaxation)합니다. 이 과정을 모든 정점이 확정될 때까지 반복합니다.
의사코드
dijkstraShortestPath(n, dist, next, start)
입력 − 전체 정점 수 n, 각 정점의 거리를 저장할 dist 리스트, 다음(경유) 정점을 저장할 next 리스트, 시작 정점(start)
출력 − 시작 정점에서 다른 모든 정점까지의 최단 경로와 비용
Begin
선택된 정점의 현재 상태를 저장할 status 리스트 생성
V의 모든 정점 u에 대해 반복:
status[u] := 미고려(unconsidered)
dist[u] := 비용 행렬 기준 시작점으로부터의 거리
next[u] := start
done
status[start] := 고려됨(considered), dist[start] := 0, next[start] := φ
while (거리가 최소인 미고려 정점 u가 존재하는 동안):
status[u] := 고려됨
V의 모든 정점 v에 대해 반복:
if status[v] = 미고려 then
if dist[v] > dist[u] + cost[u,v] then
dist[v] := dist[u] + cost[u,v]
next[v] := u
done
done
End
C++ 구현 예제
#include<iostream>
#define V 7
#define INF 999
using namespace std;
// 그래프의 비용 행렬
int costMat[V][V] = {
{0, 3, 6, INF, INF, INF, INF},
{3, 0, 2, 1, INF, INF, INF},
{6, 2, 0, 1, 4, 2, INF},
{INF, 1, 1, 0, 2, INF, 4},
{INF, INF, 4, 2, 0, 2, 1},
{INF, INF, 2, INF, 2, 0, 1},
{INF, INF, INF, 4, 1, 1, 0}
};
int minimum(int *status, int *dis, int n) {
int i, min, index;
min = INF;
for(i = 0; i<n; i++)
if(dis[i] < min && status[i] == 1) {
min = dis[i];
index = i;
}
if(status[index] == 1)
return index; // 아직 고려되지 않은 정점 중 최소 거리 반환
else
return -1; // 모든 정점이 고려된 경우
}
void dijkstra(int n, int *dist, int *next, int s) {
int status[V];
int u, v;
// 초기화 단계
for(u = 0; u<n; u++) {
status[u] = 1; // 미고려 상태의 정점
dist[u] = costMat[u][s]; // 시작점으로부터의 거리
next[u] = s;
}
// 시작 정점 처리
status[s] = 2; dist[s] = 0; next[s] = -1; //-1은 시작 정점 표시
while((u = minimum(status, dist, n)) > -1) {
status[u] = 2; // 해당 정점을 고려 완료 상태로 변경
for(v = 0; v<n; v++)
if(status[v] == 1)
if(dist[v] > dist[u] + costMat[u][v]) {
dist[v] = dist[u] + costMat[u][v]; // 거리 갱신
next[v] = u;
}
}
}
main() {
int dis[V], next[V], i, start = 0;
dijkstra(V, dis, next, start);
for(i = 0; i<V; i++)
if(i != start)
cout << start << " to " << i << ", Using: " << next[i] << ",
Cost: " << dis[i] << endl;
}
실행 결과
0 to 1, Using: 0, Cost: 3
0 to 2, Using: 1, Cost: 5
0 to 3, Using: 1, Cost: 4
0 to 4, Using: 3, Cost: 6
0 to 5, Using: 2, Cost: 7
0 to 6, Using: 4, Cost: 7
마무리
위 구현은 인접 행렬을 사용하기 때문에 구현이 직관적이고 간단하지만, 정점 수가 많아지면 O(V²)의 시간 복잡도로 인해 성능이 떨어질 수 있습니다. 실무에서는 희소 그래프(sparse graph)의 경우 인접 리스트와 우선순위 큐(최소 힙)를 조합하여 O((V+E) log V)로 최적화한 구현을 널리 사용합니다. 또한 다익스트라 알고리즘은 음수 가중치 간선이 존재하는 그래프에서는 올바른 결과를 보장하지 않으므로, 그러한 경우 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 한다는 점도 함께 기억해 두면 좋습니다.