[알고리즘] Dijkstra 알고리즘(Python)

* 개요

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다. 음의 간선이란, 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다. 알고리즘의 원리를 간략히 설명하면 다음과 같다.

 

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3번과 4번을 반복한다.

다익스트라 알고리즘은 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다. 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다. 나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 이 경로가 제일 짧은 경로로 갱신되는 것이다. 따라서 '방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인'해 그 노드에 대하여 4번 과정을 수행한다는 점에서 그리디 알고리즘으로 볼 수 있다. 다익스트라 알고리즘을 구현하는 방법은 2가지이다.

 

1. 구현하기 쉽지만 느리게 동작하는 코드
2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드

해당 포스트에서는 위의 2개의 코드를 구현해보았다.

 

* 방법1. 간단한 다익스트라 알고리즘

간단한 다익스트라 알고리즘은 O(V^2)의 시간 복잡도를 가진다. 여기서 V는 노드의 개수를 의미한다. 처음에 각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언한다. 이후에 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차 탐색)한다.

 

import sys

input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())

start = int(input())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
distance = [INF] * (n + 1)

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


def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n + 1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i

    return index


def dijkstra(start):
    distance[start] = 0
    visited[start] = True

    for j in graph[start]:
        distance[j[0]] = j[1]

    # 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
    for i in range(n - 1):
        now = get_smallest_node()
        visited[now] = True

        for j in graph[now]:
            cost = distance[now] + j[1]

            if cost < distance[j[0]]:
                distance[j[0]] = cost


dijkstra(start)

for i in range(1, n + 1):
    if distance[i] == INF:
        print("INF")

    else:
        print(distance[i])

 해당 코드의 알고리즘의 시간 복잡도는 O(V^2)이다. 왜냐하면 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하고, 현재 노드와 연결된 노드를 매번 일일이 확인하기 때문이다. 전체 노드의 개수가 5000개 이하라면 이 코드로 탐색을 진행해도 되겠지만, 노드의 개수가 10000개를 넘어간다면 해당 코드로는 시간 복잡도가 매우 커지기에 탐색을 진행하기에 적합하지 않다. 따라서 노드의 개수 및 간선의 개수가 많을 때는 '개선된 다익스트라 알고리즘'을 이용해야 한다.

 

* 방법2. 개선된 다익스트라 알고리즘

다익스트라 알고리즘을 간단히 구현하면 시간 복잡도가 O(V^2)이다. 하지만 개선된 다익스트라 알고리즘은 최악의 경우에도 시간 복잡도 O(ElogV)가 보장된다. 여기서 V는 노드의 개수이고 E는 간선의 개수를 의미한다. 간단한 다익스트라 알고리즘은 '최단 거리가 가장 짧은 노드'를 찾기 위해서, 매번 최단 거리 테이블을 선형적으로 탐색해야 했다. 하지만 최단 거리가 가장 짧은 노드를 단순히 선형적으로 찾는 것이 아니라 자료구조 heap을 이용하면 알고리즘의 시간 복잡도를 더욱 줄일 수 있다.

 

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n + 1)]
distance = [INF] * (n + 1)

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


def dijkstra(start):
    q = []

    heapq.heappush(q, (0, start))
    distance[start] = 0

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

        if distance[now] < dist:
            continue

        for node, weight in graph[now]:
            cost = dist + weight

            if cost < distance[node]:
                distance[node] = cost
                heapq.heappush(q, (cost, node))


dijkstra(start)

for i in range(1, n + 1):
    if distance[i] == INF:
        print("INF")

    else:
        print(distance[i])

위의 코드에서 확인할 수 있듯이 한 번 처리된 노드는 더 이상 처리되지 않는다. 다시 말해 큐에서 노드를 하나씩 꺼내 검사하는 반복문(while문)은 노드의 개수 V 이상의 횟수로는 반복되지 않는다. 또한 V번 반복될 때마다 각각 자신과 연결된 간선들을 모두 확인한다. 따라서 '현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인'하는 총 횟수는 총 최대 간선의 개수(E)만큼 연산이 수행될 수 있다. 중복 간선을 포함하지 않는 경우, E는 항상 V^2보다 작다. 왜냐하면 모든 노드끼리 서로 다 연결되어 있다고 했을 때 간선의 개수를 약 V^2으로 볼 수 있고 E는 항상 V^2 이하이기 때문이다. 따라서 개선된 다익스트라 알고리즘의 전체 시간 복잡도는 O(ElogV)라고 볼 수 있다.