다익스트라 알고리즘 — 최단 경로를 단계별로 이해하기

다익스트라 알고리즘은 가중 그래프에서 하나의 시작 노드로부터 최단 경로를 찾는 알고리즘입니다. 단, 모든 간선의 가중치가 음수가 아니어야 합니다. 하나의 목적지만 필요하다면 그 목적지의 거리가 확정되는 순간 바로 멈춰도 됩니다.

핵심 아이디어는 탐욕적 선택입니다. 아직 확정되지 않은 노드 중 현재까지 알려진 거리가 가장 작은 노드부터 계속 진행합니다. 이 방식이 성립하는 이유는 간선 가중치가 모두 음수가 아니기 때문입니다.

다익스트라 알고리즘이 해결하는 문제

간선에 비용이 있는 그래프에서 가장 저렴한 경로를 찾고 싶을 때 다익스트라 알고리즘을 사용합니다. 이 비용은 거리, 이동 시간, 에너지, 또는 최소화하고 싶은 다른 양을 뜻할 수 있습니다.

방향 그래프와 무방향 그래프 모두에 적용할 수 있습니다. 중요한 조건은 분명합니다. 모든 간선의 가중치는 반드시 $0$ 이상이어야 합니다.

알고리즘이 작동하는 방식

각 노드는 시작 노드로부터의 임시 거리를 하나씩 가집니다. 처음에는 시작 노드의 거리를 $0$으로 두고, 나머지 모든 노드의 거리는 $\infty$로 둡니다.

그다음 다음 과정을 반복합니다:

1. 아직 확정되지 않은 노드 중 임시 거리가 가장 작은 노드를 고릅니다.
2. 그 노드를 거쳐 갈 수 있는 각 이웃 노드를 확인합니다.
3. 새 경로가 더 저렴하면 이웃 노드의 거리를 갱신합니다.
4. 현재 노드를 확정 처리합니다.

3번 단계는 완화(relaxation)라고 부릅니다. 노드가 확정되었다는 것은 그래프에 음수 가중치 간선이 없다는 조건 아래, 그 노드의 최단 거리가 최종값이 되었다는 뜻입니다.

다익스트라 알고리즘 단계별 정리

전체 절차를 간단히 정리하면 다음과 같습니다:

1. 시작 노드를 하나 정합니다.
2. 그 노드의 거리를 $0$으로, 나머지 모든 노드의 거리를 $\infty$로 설정합니다.
3. 아직 확정되지 않은 노드 중 임시 거리가 가장 작은 노드를 선택합니다.
4. 그 노드에서 나가는 간선을 완화합니다.
5. 그 노드를 확정 처리합니다.
6. 도달 가능한 모든 노드가 확정될 때까지 반복하거나, 목표 노드가 확정되면 멈춥니다.

각 거리 갱신이 어떤 이전 노드 때문에 일어났는지도 함께 저장하면, 최종 거리뿐 아니라 실제 경로까지 복원할 수 있습니다.

최단 경로 예제

그래프의 간선 가중치가 다음과 같다고 합시다:

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

우리는 $A$에서 $D$까지의 최단 경로를 구하려고 합니다.

처음 상태는 다음과 같습니다:

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

먼저 $A$를 확정하고, 연결된 간선을 완화합니다:

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

이제 아직 확정되지 않은 노드 중 가장 작은 거리는 $C$이므로, 다음으로 $C$를 확정합니다.

$C$를 거쳐 가면:

• $C$를 통해 $B$로 가는 비용은 $1+2=3$이므로 기존의 $4$보다 좋아집니다. 따라서 $\text{dist}(B)=3$으로 갱신합니다.
• $C$를 통해 $D$로 가는 비용은 $1+5=6$이므로 $\text{dist}(D)=6$으로 설정합니다.

이제 $B$가 아직 확정되지 않은 노드 중 가장 작은 거리를 가지므로, $B$를 확정합니다.

$B$를 거쳐 $D$로 가는 비용은 다음과 같습니다:

$$3+1=4$$

이는 기존의 $6$보다 작으므로, $\text{dist}(D)$를 $6$에서 $4$로 갱신합니다.

이제 $D$가 가장 작은 미확정 노드입니다. $D$를 확정하고 멈춥니다.

최단 경로는 다음과 같습니다:

$$A \to C \to B \to D$$

총비용은 다음과 같습니다:

$$1+2+1=4$$

이 예제는 중요한 패턴을 보여 줍니다. 처음에는 더 나빠 보였던 경로 $A \to B$가 나중에 $C$를 거치면서 더 좋아졌습니다. 다익스트라 알고리즘은 $B$가 아직 확정되지 않은 동안 이런 갱신을 허용합니다. 하지만 한 번 노드가 확정되면 그 거리는 더 이상 바뀌지 않습니다.

왜 음수가 아닌 가중치가 중요한가

현재 가장 저렴한 미확정 노드의 거리가 $d$라고 합시다. 나중에 그 노드로 가는 새로운 경로가 발견되려면, 적어도 임시 거리가 $d$ 이상인 다른 미확정 노드에서 출발한 뒤 가중치가 $0$ 이상인 간선을 더해야 합니다.

따라서 그 나중 경로가 $d$보다 더 좋아질 수는 없습니다. 그래서 모든 가중치가 음수가 아닐 때는 가장 작은 임시 거리를 가진 노드를 확정해도 안전합니다.

하지만 음수 간선이 하나라도 있으면 이 논리가 깨집니다. 지금은 비싸 보이는 경로가 나중에 더 저렴해질 수 있으므로, 노드를 너무 일찍 확정하면 잘못된 답을 얻게 됩니다.

다익스트라 알고리즘에서 자주 하는 실수

음수 간선이 있는 그래프에 사용하기

음수 간선이 하나만 있어도 탐욕적 선택의 논리가 무너질 수 있습니다. 음수 가중치가 가능하다면 다른 최단 경로 알고리즘을 사용해야 합니다.

"봤다"를 "끝났다"로 착각하기

어떤 노드에 이미 임시 거리가 기록되어 있어도 아직 끝난 것이 아닐 수 있습니다. 확정된 노드만이 최종 최단 거리를 가집니다.

이전 노드 표를 저장하지 않기

거리 정보는 비용만 알려 줍니다. 실제 경로까지 알고 싶다면, 각 거리를 마지막으로 갱신한 이전 노드도 함께 저장해야 합니다.

다익스트라 알고리즘의 활용 분야

다익스트라 알고리즘은 문제를 음수가 아닌 비용을 가진 그래프 위의 이동으로 모델링할 수 있을 때 사용됩니다:

• 지도에서의 경로 탐색
• 네트워크 라우팅
• 가중 격자에서의 로봇 이동
• 이동 비용이 서로 다른 게임 경로 탐색

또한 이 알고리즘은 정확성이 특정 조건에 의존하는 대표적인 탐욕 알고리즘의 예시이기도 합니다.

비슷한 문제를 직접 해보기

노드가 다섯 개인 그래프를 그리고, 양의 간선 가중치를 넣은 뒤 거리 표를 사용해 손으로 다익스트라 알고리즘을 실행해 보세요. 다음 단계로는 새로운 그래프를 직접 만들어 보고, 각 노드가 정확히 언제 확정해도 안전해지는지 확인해 보면 좋습니다.