다익스트라 알고리즘이란?
다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 노드 간의 최단 경로를 찾는 대표적인 알고리즘입니다. SPF(Shortest Path First) 알고리즘이라고도 불리며, 도로망과 같은 실제 네트워크를 모델링하는 데 널리 활용됩니다. 이 알고리즘은 시작 정점(소스)에서 출발하여 그래프 내의 다른 모든 지점까지의 최단 경로 트리를 생성합니다.
다익스트라 알고리즘은 소스 노드로부터 최소 거리를 가지는 노드들의 집합을 점진적으로 확장해 나가면서, 단일 소스 노드에 대한 최단 경로 트리를 완성합니다.
그래프의 구성 요소
- 정점(Vertex) 또는 노드(Node): 알고리즘에서는 일반적으로 v 또는 u로 표기합니다.
- 가중치가 있는 간선(Weighted Edge): 두 노드를 연결하며, (u, v)는 간선을, w(u, v)는 그 가중치를 의미합니다.
알고리즘 동작 단계
- 소스 정점을 제외한 모든 정점의 거리를 무한대(INFINITY)로 설정하고, 소스 정점의 거리는 0으로 초기화합니다.
- 소스 정점을 (거리, 정점) 형태로 최소 우선순위 큐(min-priority queue)에 삽입합니다. 큐는 정점의 거리를 기준으로 비교합니다.
- 우선순위 큐에서 최소 거리를 가진 정점을 꺼냅니다(처음에는 소스 정점이 꺼내집니다).
- '현재 정점의 거리 + 간선의 가중치 < 다음 정점의 거리' 조건을 만족하면, 꺼낸 정점과 연결된 정점들의 거리를 갱신하고, 새로운 거리와 함께 해당 정점을 우선순위 큐에 다시 삽입합니다.
- 꺼낸 정점이 이미 방문된 정점이라면, 해당 정점은 사용하지 않고 건너뜁니다.
- 우선순위 큐가 빌 때까지 동일한 과정을 반복합니다.
그래프와 그래프 안의 하나의 소스 정점이 주어졌을 때, 소스에서 그래프의 모든 정점까지의 최단 경로를 구하는 것이 목표입니다. 여기서 G[][]는 그래프의 가중치 행렬, n은 정점의 개수, u는 시작 노드를 의미합니다.
입력 예시
G[max][max]={{0,1,0,3,10},
{1,0,5,0,0},
{0,5,0,2,1},
{3,0,2,0,6},
{10,0,1,6,0}}
n=5
u=0
출력 결과
Distance of node1=1 Path=1<-0 Distance of node2=5 Path=2<-3<-0 Distance of node3=3 Path=3<-0 Distance of node4=6 Path=4<-2<-3<-0
출력 결과를 해석하면, 노드 1까지의 최단 거리는 1이며 경로는 1←0입니다. 노드 2까지는 거리 5에 경로 2←3←0, 노드 3까지는 거리 3에 경로 3←0, 노드 4까지는 거리 6에 경로 4←2←3←0입니다.
알고리즘 상세 설명
인접 행렬 adj[][]로부터 비용 행렬 C[][]를 생성합니다. C[i][j]는 정점 i에서 정점 j로 이동할 때 드는 비용을 의미하며, 두 정점 사이에 간선이 없다면 C[i][j]는 무한대(INFINITY)로 설정됩니다.
방문 여부를 저장하는 배열 visited[]를 0으로 초기화합니다.
for(i=0;i<n;i++) visited[i]=0;
정점 0이 소스 정점이라면 visited[0]을 1로 표시합니다.
거리 배열(distance)을 생성하여, 소스 정점 0으로부터 각 정점(0번부터 n-1번까지)까지의 비용을 저장합니다.
for(i=1;i<n;i++) distance[i]=cost[0][i];
처음에는 소스 정점 자신의 거리를 0으로 설정합니다. 즉, distance[0]=0;
for(i=1;i<n;i++) visited[i]=0;
distance[w]가 최소이면서 visited[w]가 0인 정점 w를 선택하고, visited[w]를 1로 표시합니다.
소스로부터 나머지 정점들의 최단 거리를 다시 계산합니다.
이때 visited[] 배열에서 1로 표시되지 않은 정점만 거리 재계산 대상으로 삼아야 합니다. 즉, 각 정점 v에 대해 다음과 같이 처리합니다.
if(visited[v]==0) distance[v]=min(distance[v], distance[w]+cost[w][v])
C++ 전체 구현 예제
#include<iostream>
#include<stdio.h>
using namespace std;
#define INFINITY 9999
#define max 5
void dijkstra(int G[max][max],int n,int startnode);
int main() {
int G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}};
int n=5;
int u=0;
dijkstra(G,n,u);
return 0;
}
void dijkstra(int G[max][max],int n,int startnode) {
int cost[max][max],distance[max],pred[max];
int visited[max],count,mindistance,nextnode,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
for(i=0;i<n;i++) {
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1) {
mindistance=INFINITY;
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i]) {
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i]) {
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
for(i=0;i<n;i++)
if(i!=startnode) {
cout<<"\nDistance of node"<<i<<"="<<distance[i];
cout<<"\nPath="<<i;
j=i;
do {
j=pred[j];
cout<<"<-"<<j;
}while(j!=startnode);
}
}
이 구현은 인접 행렬과 선형 탐색 방식을 사용하기 때문에 시간 복잡도는 O(n²)입니다. 그래프의 크기가 커질 경우, 우선순위 큐(std::priority_queue 등)와 인접 리스트를 함께 사용하면 O((V+E)logV)로 성능을 개선할 수 있습니다.