최단 경로 문제 (1) - 다익스트라 알고리즘

최단 경로는 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제입니다. 각 지점은 정점 (vertex), 정점사이의 간선 (edge)은 길에 해당하고 가중치는 간선에 대한 시간, 거리 등의 이동비용에 해당합니다. 구성한 그래프의 형태에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재합니다. 이번 포스트에서는 그 중 가장 대표적인 다익스트라 (Dijkstra) 알고리즘을 살펴보겠습니다.

다익스타라 알고리즘은 네덜란드의 에츠허리 다익스트라가 1956년에 고안한 알고리즘으로 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하는 알고리즘입니다. 특히, 다익스타라 알고리즘은 매 상황에서 가장 비용이 적은 노드를 선택하는 그리디 알고리즘으로 분류됩니다.

알고리즘은 다음과 같이 동작합니다.

1. 출발 노드를 설정하고 각 노드에 대한 최단 거리 테이블을 초기화합니다.
2. 출발 노드부터 방문하지 않은 최단 거리가 가장 짧은 노드를 선택합니다.
3. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 업데이트하고 이 과정을 반복합니다.

EXAMPLE

다음 그래프와 각 노드 별 최단 거리를 담고 있는 테이블을 무한으로 초기환 상태에서 출발노드가 1인 경우에 대해 다익스트라 알고리즘의 동작 과정을 살펴보겠습니다.

1. Step 1

1번 노드에서 인접한 2, 3, 4 노드에 대한 최단 거리 테이블을 업데이트합니다.

노드번호	1	2	3	4	5	6
거리	0	2	5	1	무한	무한

 

2. Step 2

다음은 최단 거리가 가장 짧은 1의 인접한 노드인 4번으로 진행합니다. 4번에서는 3번과 5번이 인접한 노드인데 각각 최단 거리 테이블의 값과 비교하여 짧은 거리로 업데이트합니다.

노드번호	1	2	3	4	5	6
거리	0	2	1+3=4	1	1+1=2	무한

 

3. Step 3

다음은 방문하지 않은 노드 중 가장 짧은 2번 노드를 방문합니다. 2번 노드에서는 3, 4 노드가 인접한 노드이고 마찬가지로 최단 거리 테이블을 업데이트합니다. 이번에는 3,4 에 대해 최단 거리 테이블의 값이 이미 더 적으므로 업데이트 되지 않습니다.

노드번호	1	2	3	4	5	6
거리	0	2	4	1	2	무한

 

4. Step 4

그 다음은 방문하지 않고 최단 거리를 가지는 5번 노드를 선택합니다. 마찬가지로 최단 거리 테이블을 업데이트합니다.

노드번호	1	2	3	4	5	6
거리	0	2	2+1=3	1	2	2+2=4

 

5. Step 5

다음으로는 3번 노드를 선택합니다. 3번에서는 6번 노드가 인접점인데 비용이 크므로 테이블이 업데이트 되지 않습니다. 그 후 자연스럽게 마지막 노드 6이 남습니다. 이 경우에는 노드 6에서 나가는 방향이 없기 때문에 업데이트 되지 않고 알고리즘이 종료됩니다.

Discussion

• 다익스트라 알고리즘은 임의의 정점에서 인접점과의 거리를 계산할 때 그 정점까지의 최단거리는 이미 계산이 끝났다는 확신을 가지고 더합니다. 따라서 간선에 음수 가중치가 존재하는 경우는 처리할 수 없습니다.
• 그리디 알고리즘은 탐욕 선택 속성을 갖고 있는 최적 부분 구조인 문제로 앞의 선택이 이후 선택에 영향을 주지 않는 알고리즘의 종류를 말합니다. 즉, 다익스트라 알고리즘은 방문할 노드에 대한 계산된 최단 거리는 더 변경되지 않으므로 그리디 알고리즘의 속성을 만족합니다.
• 위의 step 별로 생각을 해보면 이미 방문한 노드는 그 노드까지의 최단 거리가 이미 결정되었으므로 다시 방문하지 않습니다. 따라서 인접점 비용을 계산할 때 인접점이 이미 방문한 노드라면 굳이 업데이트할 필요가 없습니다.
• 마지막 노드는 나가는 간선이 있더라도 이미 나머지 노드들이 방문되었기 때문에 처리할 필요가 없습니다.

 

파이썬 구현

다익스트라 알고리즘을 간단히 구현하는 방법은 매 단계마다 최단 거리가 가장 짧은 노드를 선택하기 위해 테이블을 순차 탐색하는 방법입니다. 하지만 이 방법은 전체 정점 $O(V)$에 대해서 매번 테이블을 선형 탐색해야하기 때문에 최악의 경우 $O(V^2)$의 시간 복잡도가 소요됩니다. 이를 줄이기 위해 일반적으로 다익스트라 알고리즘은 우선순위 큐 (heap)을 이용해 구현합니다.

힙은 원소의 추가와 추출이 $O(\log n)$이 소요되는 자료구조로 이를 어떻게 구현에 이용할까요? 매 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 추출하기 위해 사용합니다. 최소힙을 이용한다면 이것을 매우 자연스럽게 구현할 수 있습니다. 

먼저 힙에 (출발노드, 0)을 삽입하고 최단 거리 순으로 원소를 추출합니다. 추출한 원소의 노드가 방문되지 않았다면 최단 거리 테이블을 업데이트하고 그 노드의 인접점을 힙에 추가합니다. 힙의 특성상 항상 최소값만 추출되기 때문에 특정 노드의 거리가 테이블에 존재한다면 그 값은 이미 최단 경로이므로 무시할 수 있습니다. 코드는 다음과 같습니다.

from collections import defaultdict
from heapq import heappush, heappop

## 먼저 그래프 인접 리스트를 구성
graph = defaultdict(list)
for start_point, end_point, weight in datalist:
    graph[start_point].append((end_point, weight))

def dikstra(start):
    ## 힙 변수 설정하고 초기값 세팅 (시간, 노드)
    q = []
    heappush(q, (0, start))
    
    dist = defaultdict(int) # 최단거리 테이블
    
    while q: # 힙에 원소가 존재할 때까지
        time, node = heappop(q) # 힙에서 원소 추출
        ## 힙은 항상 최소값만을 추출하므로 
        ## node가 이미 최단거리 테이블에 있다면, 그 값은 최소값이므로 skip
        if node not in dist:
            dist[node] = time # 최단거리 테이블 업데이트
            ## 인접한 노드에 대해
            for end_point, weight in graph[node]:
                cost = time + weight # 거리를 계산하고 
                heappush(q, (cost, end_point)) # 힙에 추가
                
    ## 최단거리 테이블에 모든 노드 값이 존재한다면
    ## 모든 노드에 대한 최단거리 존재 여부 확인 가능
    if len(dist) == 전체 노드 수:
        return max(dist.values()) # 제일 오래 걸리는 경로 return할 경우    
        

 

시간 복잡도

힙으로 구현한 다익스트라 알고리즘의 시간 복잡도는 어떻게 될까요? 직관적으로 전체 과정이 모든 간선 $E$를 넣었다가 추출하는 것으로 볼 수 있습니다. 즉, while 반복문에서는 우선순위 큐에서 꺼낸 노드와 다른 인접 노드와의 관계를 확인하는 총횟수는 최대 $E$ 만큼 연산된다고 볼 수 있는 것이죠. 힙의 연산은 $O(\log n)$이므로 전체 시간 복잡도는 $O(E\log E)$로 볼 수 있습니다.

일반적으로 중복 간선이 없는 경우 (두 노드 별 간선이 오는 간선, 가는 간선 2개까지만 존재하는 경우) $E$가 $V^2$보다 작으므로 시간 복잡도는 $O(E\log V^2)$보다 작게 되는데 빅오 표기법 상 $O(E\log V)$로 표현할 수 있습니다.

 

홍머스 정리

• 그리디 알고리즘
• 우선순위 큐 (힙) 으로 구현

참조

• www.youtube.com/watch?v=F-tkqjUiik0&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=30
• <파이썬 알고리즘 인터뷰>, p373-378