728x90

최단 거리 알고리즘: 다익스트라 알고리즘

다익스트라(Dijkstra) 알고리즘은 특정 노드에서 출발하여 다른 모든 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다. 그리디 알고리즘(탐욕법)에 기반하며, 매 단계마다 가장 비용이 적은 노드를 선택하여 과정을 반복한다. 다익스트라 알고리즘은 최단 거리 정보를 1차원 리스트에 저장하고 계속 갱신하여 최종 결과를 도출한다.

다익스트라 알고리즘의 기본 동작 원리

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

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

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

구현 예시

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)]
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]

    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("INFINITY")
    else:
        print(distance[i])

간단한 다익스트라 알고리즘은 노드의 개수가 많을 경우 비효율적이다. 특히 노드의 개수가 10,000개를 넘어가면 시간 초과가 발생할 수 있다.

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

개선된 다익스트라 알고리즘은 최소 힙(Heap) 자료구조를 사용하여 최단 거리가 가장 짧은 노드를 효율적으로 선택한다. 이를 통해 시간 복잡도를 O(ElogV)로 줄일 수 있다. 여기서 E는 간선의 개수, V는 노드의 개수다.

힙(Heap)

힙은 우선순위 큐를 구현하기 위해 사용되는 자료구조다. 파이썬에서는 최소 힙이 기본적으로 제공되며, heapq 모듈을 통해 사용할 수 있다. 최소 힙을 최대 힙처럼 사용하려면 간선의 비용 정보를 음수로 변환하여 저장하면 된다.

개선된 다익스트라 알고리즘 구현 예시

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 i in graph[now]:
            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, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

이 알고리즘은 힙 구조를 사용하여 시간 복잡도를 대폭 줄였다. 따라서 노드가 10,000개 이상인 대규모 그래프에서도 사용할 수 있다.

결론

다익스트라 알고리즘은 그래프에서 단일 출발 지점에서 모든 노드로의 최단 경로를 구할 때 매우 유용하다. 간단한 다익스트라 알고리즘은 이해하기 쉽지만, 대규모 그래프에서는 비효율적이므로 개선된 다익스트라 알고리즘을 사용하는 것이 적합하다. 개선된 알고리즘은 힙(Heap) 자료구조를 사용하여 시간 복잡도를 O(ElogV)로 줄여, 실용적인 범위 내에서 동작하도록 최적화되었다.