다익스트라 알고리즘[파이썬 예제 코드]

최단 경로$($Shortest Path)를 구하는 대표적인 알고리즘인 다익스트라$($Dijkstra’s) 알고리즘에 대해서 알아보도록 하겠다.

다양한 최단 경로 문제중에서도 다익스트라 알고리즘은 한 노드에서 다른 하나의 특정 지점까지의 최단 경로를 구하는데 유용하게 사용된다.

다익스트라 알고리즘 수행과정

다익스트라 알고리즘은 너비우선탐색$($BFS) 과 우선순위 큐를 기반으로 동작한다.

아래의 그래프를 통해 다익스트라 알고리즘의 동작과정을 살펴보도록 하겠다.

$($a)

먼저 시작노드 s를 제외한 모든 노드의 거리정보를 무한대로 초기화 한다.

시작노드 s는 탐색하고 있다는 의미로 회색으로 표시한다.

$($b)

시작노드 s를 기준으로 BFS를 적용해 나간다.

s에 이웃한 노드인 t와 y에 대한 거리정보를 업데이트한다음 s의 방문을 마쳤다는 의미로 노드를 검은색으로 표시한다.

그 다음 방문하지 않은 노드들 가운데 거리가 최소인 y노드 $($y = 5, t = 10)를 탐색하게 되며 y노드를 회색으로 표시한다. $($우선순위 큐 사용)

$($c)

y에 이웃한 t, x, z에 대해 거리정보를 업데이트 한다.

$($y, t)의 경우 기존 t값 10 보다 5 + 3 = 8이 더 작기 때문에 t의 값을 8로 갱신하고 최단경로를 y를 경유하게끔 업데이트한다.

$($y, x)또한 5 + 9 = 14 < INF이므로 x값을 14로 갱신하고 $($y, z)도 7로 바꿔줍니다.

그러고 나서 y방문을 마쳤다는 의미로 y를 검은색으로 표새해 둡니다. 다음 BFS 적용대상은 미방문 노드중 거리가 7로 가장 작은 z이며 탐색대상이라는 의미인 회색으로 칠합니다.

$($d)

z를 기준으로 BFS를 적용한다. z에 이웃한 y, x에 대한 거리정보를 업데이트해야 하는데, y는 이미 검은색으로 방문 표시가 되어있으므로 x만 업데이트 해주게 된다. 7 + 6 = 13은 기존의 s와 x사이의 최단거리 14보다 작으므로, s와 x 사이의 최단거리를 13으로 바꾸고 최단경로를 z를 경유하게끔 업데이트 한다.

z방문을 마쳤다는 의미로 검은색으로 표시해 두며 다음 BFS 적용 대상은 미방문 노드중 거리가 8로 가장 작은 t이므로 회색으로 표시한다.

$($e)

t를 기준으로 BFS를 적용한다. $($t, x)인 8 + 1 = 9가 기존의 s와 x사이의 최단거리 13보다 작기 때문에 s와 x 사이의 최단거리를 9로 갱신하고 최단경로를 t를 경유하게끔 업데이트한다.

t 방문을 마쳤다는 의미로 검은색으로 칠하고 다음 BFS 적용 대상인 x를 회색으로 표시한다.

$($f)

x를 기준으로 BFS를 적용한다. 이웃한 z노드의 경우 이미 방문처리가 되어있기 때문에 처리할 이웃노드가 없으므로 x탐색을 마치고 검은색으로 표시한다.

모든 노드 방문을 마쳤다.

다익스트라 알고리즘 코드 $($Python)

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9) # 무한대 값

# 노드, 간선의 개수 입력
v, e = map(int, input().split())
# 시작지점 값 입력
start = int(input())
# 모든 간선에 대한 정보를 담는 배열
G = [[] for i in range(v + 1)]
# 최단거리 테이블을 무한대로 초기화
distance = [INF] * (v + 1)

# 모든 간선의 정보 입력
for _ in range(e):
    s, e, cost = map(int, input().split())
    # 방향 그래프인 경우
    G[s].append((e, cost))
    # 무방향 그래프의 경우 G[e].append(s, c) 추가

# 다익스트라 알고리즘
def dijkstra(start):
    # 미방문 노드 저장하는 우선순위 큐 (최단거리, 탐색노드)
    q = [(0, start)]
    # 시작노드 초기화
    distance[start] = 0

    # 큐가 빌때까지 반복. BFS수행
    while q:
        # 미방문 노드중 거리가 가장 작은 노드 삭제
        dist, curNode = heapq.heappop(q)
        # 이미 처리된 노드이면 패스
        if distance[curNode] < dist: continue
        # BFS 수행노드의 인접노드의 최단경로값을 확인
        for i in G[curNode]:
            cost = dist + i[1]
            # 현재 노드에서 인접노드로 가는 경로값이 더 작은 경우 갱신
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)

# 시작노드로 부터 각 노드까지의 최단경로를 출력
for i in range(1, v + 1):
    if distance[i] == INF: print("INFINITY")
    else: print(distance[i])

시간복잡도

위의 과정에서 살펴보았듯이 미방문 노드 가운데 최단 경로가 가장 작은 노드에 BFS를 적용하였습니다.

최단 경로가 가장 작은 노드의 경우 우선순위 큐 $($Priority_queue)를 사용하여 찾아내었는데, 우선순위 큐가 가장 커지는 경우는 모든 간선이 검사될 때마다 값이 갱신되고 우선순위 큐에 정점의 번호가 추가되는 경우이다.

이 경우, 추가는 각 간선마다 한번 일어나기 때문에, 우선순위 큐에 추가되는 원소의 수는 최대 O(E)시간 걸리고, O(E)개의 원소에 대해 삽입이 이루어 지기 때문에 전체 시간 복잡도는 O(ElogE)가 된다.

대개의 경우 그래프의 간선 개수 |E|는 |V|^2보다 작기 때문에 O(log|E|) = O(log|V|)라고 볼수있고, 따라서 시간복잡도는 O(|E|log|V|)가 된다.