[Algorithm] 다익스트라(Dijkstra) 알고리즘

안녕하세요 배트맨🦇 입니다 !

오늘은 최단 경로를 찾을 때 자주 사용되는 다익스트라(Dijkstra) 알고리즘에 대해 정리해보려고 합니다.

알고리즘의 개념과 우선순위 큐를 이용한 파이썬 코드를 구현하는 것으로 내용을 구성하려 합니다.

시작해보겠습니다!

---

다익스트라 알고리즘이란?

음의 가중치가 없는 그래프의 한 정점(頂點, Vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘(최단 경로 문제, Shortest Path Problem)이다.
- 나무 위키 -

즉, 

모든 간선에 음수가 아닌 가중치가 있는 그래프가 존재할 때,

한 노드에서 도달할 수 있는 모든 노드까지 최단 거리를 구할 수 있는 알고리즘입니다.

 

다익스트라 알고리즘을 공부하면서 느꼈던 부분은 원리가 쉽게 이해되는 반면에 구현하는 것은 낯설었고 쉽게 익혀지지 않는다는 점이었습니다. 오늘 게시글은 구현하는 것에 더 초점을 두려고 합니다.

---

알고리즘의 구현 원리

앞서 말씀드렸듯이 우선순위 큐를 사용하는 방법으로 구현할 예정입니다.

1. 출발 노드를 정하고, 최단거리 테이블을 초기화합니다.

2. 현재 노드와 연결된 다른 노드의 비용을 계산하여 최단 거리 테이블을 업데이트합니다.

3. 업데이트한 노드를 탐색해야 할 노드 큐에 넣습니다.

4. 탐색해야할 노드 큐에서 가중치가 가장 작은 노드를 다음 노드로 선택합니다.

5. 위 2, 3, 4번 과정을 반복합니다.

 

예시를 들어보겠습니다.

(직접 그림을 그려보니까 들인 시간과 결과물이 반비례 하네요 !)

시간 ∝ $ \frac{1}{완성도} $

 

1. 출발 노드는 1번으로 정하고, 최단거리 테이블을 무한대로 초기화합니다.

노드 번호	1	2	3	4	5
최단거리	0	INF	INF	INF	INF

2. 출발 노드(1번)와 연결된 노드(2번, 3번, 5번)의 현재 최단거리는 모두 무한대이므로 갱신합니다. 갱신된 노드는 탐색해야 할 노드 큐에 넣습니다. 큐에 넣을 때 (가중치, 노드번호)를 같이 넣습니다.

노드 번호	1	2	3	4	5
최단거리	0	2	7	INF	4

3. 탐색해야할 노드 중 가중치가 가장 작은 2번 노드를 선택합니다. 2번 노드를 거쳐 3번으로 가면 3번 노드의 최단거리가 5이고 현재 최단거리 표에는 7이므로 표를 업데이트합니다. 

노드 번호	1	2	3	4	5
최단거리	0	2	$ min(7, 2+3) $	INF	4

4. 다음 탐색해야할 노드는 5번 노드입니다. 4번 노드의 최단거리를 갱신할 수 있습니다.

노드 번호	1	2	3	4	5
최단거리	0	2	5	$ min(INF, 4+3) $	4

5. 다음 탐색할 노드는 3번 노드이고, 4번 노드를 갱신할 수 있습니다.

노드 번호	1	2	3	4	5
최단거리	0	2	5	$ min(7, 5+1) $	4

6. 5번까지의 과정이 끝나고 탐색해야할 노드 큐에는 (7,3)과 (7,4)가 남아있습니다. 표에 저장된 3번 노드와 4번 노드의 최단거리가 7보다 작기 때문에 (7,3)과 (7,4)는 가지치기를 통해 생략할 수 있습니다.

노드 번호	1	2	3	4	5
최단거리	0	2	5	6	4

이제 코드로 구현해보겠습니다.

---

Dijkstra by Python

import heapq
import sys
input = sys.stdin.readline

# v = 5, e = 8
v, e = map(int, input().split()) 
graph = [[] for _ in range(v+1)]
INF = 1e9

for _ in range(e):
    a, b, cost = map(int, input().split())
    graph[a].append((b, cost))

최소 힙 사용을 위해 heapq 라이브러리를 사용합니다.

v와 e는 각각 노드의 개수와 간선의 개수입니다. 위의 예시에서는 노드가 5개 간선이 총 8개였습니다.

INF 변수는 최단거리 리스트를 초기화할 때 사용할 무한대 변수입니다.

간선의 입력은 (출발 노드, 도착 노드, 가중치)로 받습니다.

아래는 최단거리 리스트를 반환하는 다익스트라 함수입니다.

def dijkstra(start):
    q = []
    distance = [INF] * (v + 1)
    distance[0] = -1
    
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for node_index, node_cost in graph[now]:
            cost = dist + node_cost

            if distance[node_index] > cost:
                distance[node_index] = cost
                heapq.heappush(q, (cost, node_index))

    return distance

distance[0]을 -1로 설정했는데 상황에 맞게 초기화하면 됩니다. 

(파이썬은 기본적으로 제공하는 최소 힙을합니다. 힙 구조에 대한 게시글은 추후에 올려서 링크를 걸도록 하겠습니다 !)

힙에 push 할 때는 (가중치, 노드 번호) 순서쌍으로 넣어줌으로써 가중치가 낮은 것이 루트 노드로 올 수 있도록 합니다.

while문 내부의 첫 번째 if문은 탐색할 노드의 최단거리가 이미 더 작은 값으로 설정되었기 때문에 탐색하지 않아도 될 노드를 가지치기하기 위함입니다.

현재 탐색 중인 노드와 연결된 간선을 for문에서 차례로 돌며 최단거리 그래프와 비교합니다. 힙에 탐색할 노드가 남아있지 않다면 while문을 빠져나와 최단거리 리스트를 반환합니다.

---

다익스트라 알고리즘의 시간 복잡도

우선순위 큐를 활용한 다익스트라 알고리즘의 시간 복잡도는 $ O(ElogV) $입니다.

(E : 간선의 개수, V : 노드의 개수)

우선순위 큐에서 꺼낸 노드를 탐색할 때 해당 노드와 연결된 노드들만 탐색하므로 최악의 경우에 E만큼 반복합니다.

따라서 우선순위 큐를 활용한 다익스트라 알고리즘은 E개의 간선을 힙에 넣었다가 다시 빼는 것으로 볼 수 있습니다. 힙 자료구조에서 push와 pop은 모두 $ O(logN) $의 시간 복잡도를 가지므로 $ O(ElogE) $가 되게 됩니다. 이때, E는 $ V^{2} $ 보다 작거나 같으므로 $ logE $는 $ logV^{2} $보다 작거나 같습니다. 따라서 하나의 간선에 대해 걸리는 시간 복잡도는 $ O(logV ) $라고 볼 수 있으며 최악의 경우 최대 간선 개수를 고려해 총 시간 복잡도는 $ O(ElogV) $ 가 됩니다.

 

감사합니다 !