다익스트라(Dijkstra) 알고리즘으로 최단 경로 문제 해결하기

최단 경로 문제란 ?

우리가 길을 찾을 때 가장 빠른 길을 고민하듯이, 컴퓨터 과학에도 비슷한 문제가 있다. 바로 최단 경로 문제(Shortest Path Problem)이다. 이 문제는 가중 그래프에서 한 정점(시작점)에서 다른 정점(도착점)까지 가는 경로 중 가중치의 합이 최소가 되는 경로를 찾는 것을 목표로 한다. 여기서 가중치는 간선(edge)에 붙은 숫자로, 거리, 시간, 비용 등을 나타낼 수 있다.

예를 들어, 도시 A에서 도시 C로 가는 길이 두 개 있다고 해보자. 하나는 직진해서 10km이고, 다른 하나는 B를 거쳐서 7km라면, 당연히 7km인 경로를 선택할 것이다. 최단 경로 문제는 이런 상황을 수학적으로 해결하는 방법이다. 이번 포스팅에서는 이 문제를 효율적으로 푸는 방법 중 하나인 다익스트라 알고리즘(Dijkstra’s Algorithm)을 알아보고, 실생활에서의 활용 사례도 간단히 살펴보려고 한다.

 

다익스트라 알고리즘: 어떻게 동작할까?

다익스트라 알고리즘은 한 정점(vertex)에서 다른 모든 정점까지의 최단 경로를 찾는 데 최적화된 알고리즘이다. 이 알고리즘은 가중치가 음수가 아닌 경우에만 제대로 작동한다는 점이 특징이다. 그럼 간단히 작동 원리를 단계별로 알아보자.

 

1. 초기화

• 시작 정점의 거리를 0으로, 나머지 모든 정점의 거리를 무한대(∞)로 설정한다.
• 아직 방문하지 않은 정점들을 모아놓은 집합(Q)을 만든다.

2. 탐색과 갱신

 

• 방문하지 않은 정점 중에서 현재까지의 거리(d)가 가장 작은 정점을 선택한다.
• 그 정점을 '방문 처리'하고, 이 꼭지점과 연결된 인접 정점들의 거리를 갱신한다.
• 갱신 방식: 기존 거리와 '현재 정점을 거쳐 가는 거리'를 비교해서 더 작은 값을 선택한다.
  • 예: d[v] = min(d[v], d[u] + w(u, v)) (여기서 w(u, v)는 두 정점 간 가중치)

 3. 반복

• 모든 정점을 방문할 때까지 위 과정을 반복한다.

 

다익스트라 알고리즘을 의사코드(pseudocode)로 구현하면 다음과 같다. 

function Dijkstra(G, w, s)
{ 	foreach vertex v in V[G]
	{ 	d[v] ← ∞;
	}
	d[s] ← 0;
	Q ← V[G];
	while Q ≠ ∅ do
    { 	d[u]의 값이 최소인 정점 u ∈ Q를 선택;
		Q ← Q - {u};
		Q’ ← { v ∈ Q | v는 u와 인접 };
		foreach vertex v in Q’
		{	  d[v] ← min{ d[v], d[u] + w(u,v) };
		}
	}
}

이 의사코드를 한 줄씩 해석해보자. 

의사코드 해석

1. 함수 정의

function Dijkstra(G, w, s)

• G: 그래프를 나타낸다. 정점(Vertex)과 변(Edge)으로 이루어진 구조이다.
• w: 두 정점 사이의 가중치(거리)를 나타내는 함수이다. 예를 들어, w(u, v)는 정점 u에서 v까지의 거리이다.
• s: 시작 정점이다. 여기서부터 최단 경로를 계산한다.

2. 초기화

{ 	foreach vertex v in V[G]
	{ 	d[v] ← ∞;
	}
	d[s] ← 0;

• V[G]: 그래프 G에 있는 모든 정점들의 집합이다.
• d[v]: 시작 정점 s에서 정점 v까지의 (현재까지 알려진) 최단 거리를 저장하는 배열이다.
• 모든 정점 v에 대해 d[v]를 무한대(∞)로 초기화한다. 즉, 처음에는 경로를 모른다고 설정하는 것이다.
• 시작 정점 s의 거리 d[s]는 0으로 설정한다. (자기 자신까지의 거리는 0이기 때문.)

	Q ← V[G];

• Q: 아직 처리하지 않은 정점들을 저장하는 집합이다. 처음에는 그래프의 모든 정점을 넣는다.

3. 메인 루프

	while Q ≠ ∅ do

• Q가 비어 있지 않은 동안 반복한다. 즉, 모든 정점을 처리할 때까지 계속한다.

    { 	d[u]의 값이 최소인 정점 u ∈ Q를 선택;
		Q ← Q - {u};

• Q에 남아 있는 정점 중에서 d[u] 값(현재까지의 최단 거리)이 가장 작은 정점 u를 선택한다. 가장 가까운 정점을 찾는 과정이다.
• 선택한 정점 u를 Q에서 제거한다. 이 정점은 이제 처리된 것.

		Q’ ← { v ∈ Q | v는 u와 인접 };

• Q’: Q에 남아 있는 정점 중에서 u와 인접한(간선으로 연결된) 정점들의 집합이다. 즉, u에서 갈 수 있는 인접 정점들만 모은 것.

		foreach vertex v in Q’
		{	  d[v] ← min{ d[v], d[u] + w(u,v) };
		}

• Q’에 있는 각 정점 v에 대해 거리를 갱신한다.
• d[v]: 기존에 계산된 v까지의 최단 거리.
• d[u] + w(u, v): u를 거쳐서 v로 가는 경로의 거리.
• min{ d[v], d[u] + w(u,v) }: 두 값 중 더 작은 값을 선택해서 d[v]를 업데이트한다. 더 짧은 경로를 찾으면 갱신하는 것.

전체 흐름을 요약하면 다음과 같다.

1. 모든 정점의 거리를 무한대로 설정하고, 시작점의 거리를 0으로 초기화.
2. 아직 처리하지 않은 정점들(Q) 중에서 가장 가까운 정점(u)을 선택.
3. u를 제거하고, u와 연결된 인접 정점들의 거리를 갱신.
4. 모든 정점을 처리할 때까지 반복.

 

예시로 이해하기

 

시작 정점이 a라면:

1. 처음: d[a] = 0, d[b] = ∞, d[c] = ∞
2. a 선택 → b와 c 갱신: d[b] = 4, d[c] = 10
3. b 선택 → c 갱신: d[c] = min(10, 4+3) = 7
4. c 선택 → 더 이상 갱신할 인접 정점 없음.
5. 결과: a에서 b까지 4, c까지 7.

컴퓨터 과학에서 다익스트라 알고리즘의 활용 예

1. 네비게이션 시스템

GPS나 내비게이션 앱(예: 구글 맵스, 카카오내비)은 도로망을 그래프로 보고, 도로의 길이(거리)나 교통 상황(가중치)을 기반으로 최단 경로를 계산한다. 다익스트라 알고리즘은 이런 상황에서 출발지에서 목적지까지 가장 빠른 길을 찾는 데 사용된다.

2. 네트워크 라우팅

인터넷에서 데이터 패킷이 한 서버에서 다른 서버로 이동할 때, 네트워크 노드 간 최적 경로를 찾는 데 다익스트라가 쓰인다. 예를 들어, OSPF(Open Shortest Path First)라는 라우팅 프로토콜은 이 알고리즘을 기반으로 동작한다.

 

3. 게임 개발

전략 게임에서 유닛이 A 지점에서 B 지점으로 이동할 때, 지형의 비용(평지, 산, 강 등)을 가중치로 삼아 최적 경로를 계산하는 데 활용된다.