다익스트라 알고리즘

왜 배우는가: 교통수요예측의 통행배정 단계에서 경로를 고르는 기본 계산 도구이기 때문이다. GPS 내비게이션 등 실무 경로 탐색의 바탕 원리이기도 하다. 시험에서도 통행배정 맥락과 단독 정의 문항으로 나온 바 있다.

출제 이력: 제135회 3교시 1번, 제114회 1교시 2번

1. 한 줄 정의와 핵심 키워드

다익스트라 알고리즘은 가중치 그래프에서 출발 노드로부터 모든 노드까지의 최단경로를 구하는 그리디 알고리즘이다.

정의의 핵심은 세 가지다. 대상이 가중치 그래프라는 점, 한 출발점에서 나머지 전체 노드까지 구한다는 점, 그리고 그리디 방식이라는 점이다. 한 쌍의 출발점과 도착점만 구하는 방식과 달리 한 번의 실행으로 출발 노드에서 모든 노드까지의 경로를 얻는다. 모든 쌍의 최단경로를 구하는 플로이드 방식과 구분되는 점이다.

핵심 키워드는 다음과 같다.

• 최단경로(Shortest Path): 두 노드를 잇는 경로 중 간선 가중치의 합이 최소인 경로다.
• 그리디 알고리즘(Greedy Algorithm): 매 단계에서 현재 가장 좋은 선택을 하는 방식이다.
• 가중치 그래프(Weighted Graph): 간선마다 거리·시간·비용 값이 붙은 그래프다.
• 영구 레이블(Permanent Label): 최단거리가 확정된 노드에 붙은 값이다.
• 작업 레이블(Working Label): 아직 확정되지 않은 노드에 붙은 임시 거리 값이다.
• 최단경로 트리(Shortest Path Tree): 출발 노드를 뿌리로 한 최단경로의 연결 구조다.

이 알고리즘은 최단경로 기법 중 그리디 계열에 속한다. 동적계획법 계열인 플로이드 방식과 함께 자주 비교되며, 비교는 6절 참고.

2. 개념 풀이

쉬운 말로 풀면 다익스트라 알고리즘은 출발지에서 가장 가까운 곳부터 차례로 확정해 나가며 길을 찾는 방법이다. 길마다 거리나 통행시간 같은 비용이 붙어 있을 때 목적지까지 가장 싼 길을 찾는다. 출발지에서 물결이 퍼져 나가듯 가까운 노드부터 탐색 범위를 넓혀 간다고 생각하면 이해가 쉽다.

정식 정의는 다음과 같다. 다익스트라 알고리즘(Dijkstra Algorithm)은 가중치 그래프에서 한 출발 노드에서 나머지 모든 노드까지의 최단경로를 구하는 방법이다. 탐색이 진행되면서 각 노드의 최단거리가 하나씩 확정되고, 결과는 최단경로 트리로 얻는다.

알고리즘의 바탕에는 그리디 알고리즘(Greedy Algorithm)의 원리가 있다. 그리디 방식은 전후 상황을 모두 따지지 않고 현재 시점에서 최선으로 보이는 선택을 이어 가는 방식이다. 다익스트라 알고리즘은 아직 확정되지 않은 노드 가운데 작업 레이블이 가장 작은 노드를 고르는 것으로 이 원리를 적용한다.

영구 레이블(Permanent Label)은 출발 노드에서 그 노드까지의 최단거리가 확정된 값이다. 출발 노드에는 처음부터 영구 레이블 0을 준다. 한 번 확정된 값은 이후 단계에서 바뀌지 않는다.

작업 레이블(Working Label)은 아직 확정되지 않은 노드에 임시로 붙는 거리 값이다. 이미 확정된 노드를 거쳐 더 짧은 경로가 발견되면 값을 낮추고, 그렇지 않으면 기존 값을 그대로 둔다.

가중치(Weight)는 간선에 붙은 비용이다. 이 알고리즘은 가중치 0 이상인 그래프에서만 정확한 최단경로를 보장한다. 음수 가중치가 있으면 이미 확정한 노드의 거리가 나중에 줄어들 수 있어 그리디 원리가 깨진다. 방향 그래프와 무향 그래프 모두에 적용할 수 있다.

최단경로 트리(Shortest Path Tree)는 출발 노드를 뿌리로 하여 모든 노드의 최단경로를 이은 구조다. 알고리즘이 끝나면 이 트리가 결과로 남는다.

가상의 예로 설명하면 이해가 빠르다. 출발 노드 A에서 B로 가는 간선 가중치가 1, A에서 C로 가는 간선 가중치가 4, B에서 C로 가는 간선 가중치가 2인 세 노드 그래프를 보자. A의 영구 레이블은 0이다. B와 C의 작업 레이블은 각각 1과 4가 된다. B를 확정하면 C는 1+2=3으로 갱신되어 4보다 작아진다. 따라서 A에서 C까지의 최단경로는 A-B-C이고 비용은 3이다.

3. 등장 배경과 필요성

다익스트라 알고리즘은 네덜란드 출신 컴퓨터 과학자 Edsger W. Dijkstra가 1956년에 착안하여 1959년에 발표하였다. 이름은 만든 사람의 이름에서 따왔다.

교통 분야에서 최단경로가 필요한 까닭은 교통수요예측의 통행배정 단계에 있다. 통행배정은 기존 교통수요예측 모형의 네 번째 단계다. 기종점 통행을 도로망 링크에 나누어 싣는 것이 통행배정의 역할이다. 이때 각 기종점 쌍(Origin-Destination Pair)마다 통행이 지나갈 최소 비용 경로를 찾아야 한다.

구역 하나를 출발지로 보면 나머지 n-1개 구역이 도착지 후보가 된다. 고려할 경로 수가 빠르게 늘어나므로 모든 경로를 하나씩 나열하는 방식은 대규모 망에서 현실적이지 않다. 그래서 출발 구역마다 한 번의 탐색으로 최단경로 트리를 얻는 방법이 필요하다.

또한 혼잡이 생기면 링크의 통행시간이 바뀌어 최단경로도 달라진다. 이 때문에 링크 비용을 갱신하면서 최단경로를 다시 구하는 연구가 이어져 왔다. 실시간 주행 데이터를 이용해 동적 가중치로 최단 통행시간 경로를 구하는 연구도 발표되었다.

배정 결과는 링크별 교통량과 통행속도로 정리된다. 이 값은 시설 수요와 비용·편익을 산정하는 입력값이 된다. 따라서 최단경로 계산이 정확해야 배정 결과 전체가 믿을 만해진다.

실무에서는 GPS 기반 내비게이션, 지하철 노선도의 경로 검색, 수송 시스템 등에 최단경로 기법이 쓰인다. 이런 서비스는 모두 출발지에서 목적지까지 가장 빠른 길을 빠르게 찾아야 한다는 공통 요구를 가진다. 교통수요예측에서는 같은 원리가 대규모 도로망 전체에 반복 적용된다.

4. 구성요소·원리·절차

다익스트라 알고리즘은 그래프의 구조와 거리 값을 다루는 몇 가지 요소로 이루어진다. 각 요소의 역할은 다음 표와 같다.

정점과 간선은 그래프의 구조를 정하고, 가중치는 구간의 비용을 정한다. 잠정 거리와 확정 집합은 탐색이 진행되면서 값이 바뀌는 상태 값이다. 그래프를 저장하는 방식도 계산량에 영향을 준다. 인접 행렬은 모든 정점 쌍마다 칸을 가지므로 공간이 V^2에 비례한다. 인접 리스트는 간선 수에 비례하는 공간만 쓴다. 교통망처럼 간선이 적은 그래프는 인접 리스트가 적합하다.

그리디(Greedy) 방식이 이 알고리즘의 원리다. 매 단계에서 확정되지 않은 정점 가운데 잠정 거리가 가장 작은 정점을 고른다. 그 정점의 거리를 확정하면 확정된 노드의 최단거리는 이후 바뀌지 않는다. 이 성질이 성립하는 이유는 다음과 같다. 확정되지 않은 정점을 거치지 않고 도착 정점에 이르는 경로는 없다. 그런데 그 미확정 정점들의 거리는 선택된 정점의 잠정 거리보다 작을 수 없다. 간선 가중치가 0 이상이므로 중간에 거쳐 가도 거리가 줄지 않는다. 그래서 선택된 정점의 잠정 거리가 곧 최단거리가 된다. 가중치가 음수이면 이 논리가 깨진다. 뒤에 발견된 간선이 이미 확정한 거리를 더 줄일 수 있기 때문이다.

정점 u를 확정한 뒤에는 u와 간선으로 이어진 정점 v마다 완화(Relaxation)를 수행한다. 완화는 u를 거쳐 가는 길이 지금의 잠정 거리보다 짧으면 v의 거리를 갱신하는 작업이다. 식은 다음과 같다.

$d(v) := min(d(v), d(u) + w(u,v))$

d(v)는 v의 잠정 거리, d(u)는 확정된 u의 거리, w(u,v)는 u에서 v로 가는 간선의 가중치다. 가중치의 단위는 통행시간이면 초나 분, 거리이면 m나 km를 쓴다. 갱신될 때마다 v의 선행 정점을 u로 기록한다. 이 기록이 나중에 경로를 되짚는 근거가 된다.

절차는 다음 순서로 진행한다.

• 출발 정점의 잠정 거리를 0으로 두고, 나머지 정점은 무한대로 둔다.
• 확정되지 않은 정점 가운데 잠정 거리가 가장 작은 정점 u를 고르고 확정한다.
• u와 연결된 정점마다 완화를 수행하고 선행 정점을 기록한다.
• 확정되지 않은 정점이 없어질 때까지 2와 3을 반복한다.
• 도착 정점에서 선행 정점을 따라 거슬러 올라가 경로를 복원한다.

1번 단계의 무한대는 아직 도달 경로가 없음을 뜻한다. 도달할 수 없는 정점은 끝까지 무한대로 남는다. 아래 흐름도는 이 절차를 그린 것이다. 되돌아가는 화살표가 2와 3의 반복 구간이다.

계산량은 정점을 고르는 자료구조에 따라 달라진다. 배열에서 최솟값을 매번 선형으로 찾으면 계산량은 O(V^2)이다. 최소 힙 같은 우선순위 큐를 쓰면 O((V+E) log V)이다. 피보나치 힙을 쓰면 O(E + V log V)이다. 교통망은 정점에 비해 간선이 적은 희소 그래프이므로 우선순위 큐 구현이 실무에서 많이 쓰인다. 교통수요예측의 통행배정 단계에서는 이 절차로 출발지에서 목적지까지 최단경로 하나를 찾고, 그 경로에 통행량을 싣는다. 이 탐색은 출발지마다 반복된다.

5. 관련 법령·기준·표준

다익스트라 알고리즘 자체를 규정하는 법령이나 고시는 없다. 아래 기준은 알고리즘의 적용 조건과 계산량에 관한 이론 기준이다. 통행배정에서 쓰는 교통 기준과는 구분해서 본다.

표의 첫 행은 적용 조건이다. 가중치가 음수이면 확정 원리가 성립하지 않으므로 이 알고리즘을 쓸 수 없다. 음수 간선이 있는 경우에는 벨만-포드 알고리즘으로 바꾼다. 계산량 행은 구현 방식이 탐색 속도를 바꾼다는 점을 보여준다.

교통 분야에서 가중치는 링크의 통행시간이다. 링크 통행시간은 교통량에 따라 늘어나므로, 통행배정에서는 가중치를 갱신하며 최단경로 탐색을 여러 번 반복한다. 이 반복으로 배정 결과가 수렴하는지 확인한다. 수렴 기준과 배정 방법은 해당 용역의 지침이나 과업지시서에 따른다.

이 알고리즘은 1956년에 착안되어 1959년에 발표되었다. 법정 기준이 아니므로 시행일과 개정 연혁은 해당하지 않는다. 답안에서 기준을 말할 때는 적용 조건과 계산량을 함께 쓴다.

6. 유형과 비교

통행배정 단계에서 쓰는 최단경로 기법은 한 출발지에서 모든 노드까지의 최단거리를 구하는 방식과 모든 노드 쌍의 최단거리를 구하는 방식으로 나뉜다. 다익스트라 알고리즘은 단일 출발점 최단경로(Single-Source Shortest Path)를 구하는 대표 기법이다. 같은 목적의 다른 알고리즘과는 적용 조건과 계산량이 다르다.