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

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

다익스트라 알고리즘(Dijkstra's Algorithm)?

음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이다. 최단 경로를 찾는 알고리즘 중 가장 기본적인 알고리즘이라 할 수 있다. 최단거리 알고리즘이므로 BFS를 기본으로 한다.

모든 노드들에 대해 각 노드들의 최단 거리를 구하는 알고리즘은 플로이드-워셜 알고리즘으로 다음에 다루도록 한다.

다익스트라 알고리즘 동작

다익스트라 알고리즘은 다음과 같다.

0. 출발 노드와 인접한 모든 노드에 대해 출발점으로부터의 거리 배열의 값으로 한계로 설정한 최대값을 입력한다. 그리고 출발점의 값은 0이다.
1. 현재 노드를 설정(A 노드)한다.
2. 현재 노드(A 노드)로부터 갈 수 있는 임의의 인접 노드(B 노드)에 대해 출발점으로부터 A 노드까지의 거리 + A 노드에서 B 노드까지의 거리와 출발점에서 B 노드까지의 거리를 비교한다.(min(d[A] + g[A][B], d[B]))
3. 만약 출발점에서 B 노드까지의 거리보다 A를 경유한 거리가 더 짧다면 d[B]를 갱신한다.
4. 현재 노드(A)의 모든 인접 노드(B)에 대해 2, 3번 과정을 수행했으면 방문 완료 처리를 하여 중복 탐색을 방지한다.
5. '방문 완료' 마킹이 되지 않은 노드 V들 중 가운데 출발점으로부터 거리가 가장 짧은 노드를 선정해 현재 노드로 설정한다. (V -> A노드)
6. 도착 노드가 방문 완료 상태이거나 미방문 노드가 없을 때까지 1~5번 과정을 반복한다.

만약 INF로 값이 갱신되지 않으면 출발점에서 갱신되지 않은 좌표 노드까지는 경로가 존재하지 않음을 의미한다.

유향 그래프에 대해 다익스트라 알고리즘을 차례대로 적용해보자.

위의 그래프에 대해 출발점을 1번 노드라 하고 각 노드에 대한 최단 경로를 구해야 한다.

a를 보면 현재 노드가 1이고 나머지는 무한대로 초기화되어 있는 배열에 인접 노드의 값을 입력한다. 이후 1번 노드에서는 더 이상 탐색할 노드가 없으므로 visit 배열에 체크한 뒤 미방문 노드 중 출발점과 거리가 가장 가까운 노드에 대해 검색한다. 검색 결과 3번 노드가 제일 가까우므로 q에 넣고 다음 단계로 진행한다.

b를 보면 q에서 pop하여 얻은 현재 노드는 3번 노드다. 이에 대해 인접한 미방문 노드 중 4번 노드를 갱신할 수 있다. 그리고 탐색을 마친 뒤 다음 노드를 검색하면 2번 노드이므로 q에 넣는다.

c의 경우 현재 노드가 2번 노드가 되었다. 인접 노드는 4, 5번 노드이므로 dist 배열의 값을 갱신한다. 출발점과 4번 노드와의 거리는 이전 3번 노드에서 탐색했을 땐 4였는데 2번 노드에서 탐색하면 3이 나온다. 더 작은 값이므로 기존 입력된 값을 교체해야 한다.

이와 같은 방식으로 d, e, f를 수행하면 [0, 2, 1, 3, 4, 5]의 배열을 얻을 수 있고 이는 1번 노드에서 출발했을 때 1부터 6번 노드까지의 최단 경로 길이를 의미한다.

다익스트라 알고리즘 구현 - 우선순위 큐

from collections import defaultdict
import heapq
infos = [[1, 2, 2], [1, 3, 1], [2, 4, 1], [2, 5, 2], [3, 4, 3],
         [4, 5, 1], [5, 6, 1]]
start = 1
graph = defaultdict(list)
# INF 값이 크기 때문에 노드가 많을 경우 크기/속도 고려하여 defaultdict 사용
dist = defaultdict(int)
q = [(0, start)]  # 출발지와의 거리 기준 min heap
for v, w, d in infos:
    graph[v].append([w, d])
while q:
    cost, node = heapq.heappop(q)  # cost 기준 가장 작은 값 출력
    if node not in dist:  # 아직 등록이 안되어 있으면
        dist[node] = cost  # 이전 넣은 값이 있어도 최소 힙 추출되어 괜찮다.
        for x, c in graph[node]:  # 각 인접 노드에 대해
            alt = cost + c  # 경로 값 계산
            heapq.heappush(q, [alt, x])  # heap에 추가
print(dist)

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

한 노드에서 모든 간선에 대해 탐색을 진행하므로 모든 노드에 대해서 $O(E)$가 소요되고 그에 따라 우선순위 큐에 들어갈 수 있는 최대 개수도 $O(E)$이다. 여기에 일반적으로 힙 연산의 시간복잡도는 $O(log\ n)$이므로 E개의 원소에 대해 연산을 진행하면 $O(Elog\ E)$로 표현할 수 있다. 다만, $E\le V^2$(모든 노드에 대해 자기 자신을 제외한 모든 노드로의 경로가 존재하는 경우)이라 하면 $O(Elog\ V^2) = O(Elog\ V)$가 되어 우선순위 큐를 사용한 다익스트라 알고리즘의 시간복잡도는 $O(Elog\ V)$라고 보통 이야기한다.

우선순위큐가 불리한 경우

E가 V보다 훨씬 크다면 $V< E$가 되어 다소 불리하다. 따라서 입력 범위를 따져봤을 때 V가 작거나 E가 매우 크다면 우선순위큐가 더 느려질 수 있기 때문에 정점 V를 기준으로 탐색함이 더 빠르다. 이 경우 시간복잡도는 $O(V^2)$가 되겠다.

INF = 100000000  # 최대값 설정
# 1부터 N까지의 정점이 있다고 가정
infos = [[1, 2, 2], [1, 3, 1], [2, 4, 1], [2, 5, 2], [3, 4, 3],
         [4, 5, 1], [5, 6, 1]]
V = 6  # 정점의 개수가 주어졌다고 할 때
graph = [[INF for _ in range(V + 1)] for _ in range(V + 1)]
s = 1

for v, w, d in infos:
    graph[v][w] = d  # 주어진 간선 정보 입력
for i in range(V):
    graph[i][i] = 0  # 제자리는 0으로 설정

visited = [False] * (V + 1)
dist = [INF] * (V + 1)  # 모두 최대값으로 설정
dist[s], visited[s] = 0, True  # 출발점은 0, 방문처리

for i in range(1, V + 1):
    dist[i] = graph[start][i]  # 출발점 - 인접노드 길이 갱신

while True:
    cost = INF
    for i in range(1, V + 1):  # 인접 노드들에 대해
        if not visited[i] and dist[i] < cost:  # 경로가 짧은 정점이면
            s = i  # 이후 출발 노드로 갱신
            cost = dist[i]  # 경로값도 갱신
    if cost == INF:
        break  # 갱신되지 않으면 더 이상 갈 경로가 없음을 의미 = 종료

    visited[s] = 1  # 탐색 노드 갱신
    for i in range(1, V + 1):  # 각 정점에 대해 최단경로 탐색
        if not visited[i] and dist[s] + graph[s][i] < dist[i]:
            dist[i] = dist[s] + graph[s][i]  # 조건 만족 시 갱신
print(dist)