[알고리즘 이론] 최단 경로 알고리즘(1) - 다익스트라 최단 경로 알고리즘

최단 경로 문제

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다.

 

최단 경로 문제의 상황은 다음과 같이 다양하다.

• 한 지점에서 다른 한 지점까지의 최단 경로
• 한 지점에서 다른 모든 지점까지의 최단 경로
• 모든 지점에서 다른 모든 지점까지의 최단 경로

 

최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 노드로 표현되고, 지점 간 연결된 도로는 그래프에서 간선으로 표현된다. 또한 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 더 많이 출제된다. 따라서 포스팅에서도 최단 경로가 아닌 최단 거리를 출력하는 코드를 구현할 것이다.

 

컴퓨터공학과 학부 수준에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜 알고리즘, 벨만 포드 알고리즘 이렇게 3가지이다. 오늘은 이 중 다익스트라 알고리즘에 대해 알아보자.

---

 

다익스트라(Dijkstra) 최단 경로 알고리즘

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 단, '음의 간선'이 없을 때 정상적으로 동작한다.

 

다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다. 또한 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않기 때문에 그리디 알고리즘을 통해 최적의 해를 찾을 수 있다. 다익스트라 최단 경로 알고리즘의 기본 동작 과정은 다음과 같다.

 

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

 

---

다익스트라 알고리즘 구현

1. 순차 탐색을 이용한 간단한 방법

방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 순차 탐색을 이용하여 코드를 구현할 수 있다. 

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

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())     # a번 노드에서 b번 노드로 가는 비용 c
    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])

V를 노드의 개수라고 할 때, 위 코드의 시간복잡도는 O(V^2)이다. 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하고 현재 노드와 연결된 노드를 매번  일일이 확인해야 하기 때문이다. 따라서 최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 위 코드로도 문제를 무리 없이 풀 수 있다. 하지만 노드의 개수가 10,000개를 넘어가는 문제라면 이 코드로는 시간 초과를 받을 것이다. 이 경우 '개선된 다익스트라 알고리즘'을 이용해야 한다.

 

 

2. 최소 힙(우선순위 큐)를 이용한 개선된 방법

방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해 최소 힙(우선순위 큐)을 사용한다. 파이썬의 heapq 라이브러리는 원소로 튜플을 받으면 튜플의 첫 번째 원소를 기준으로 우선순위 큐를 구성한다. 따라서 (거리, 노드 번호) 와 같은 형식으로 데이터를 구성해 우선순위 큐에 넣으면 거리순으로 정렬되어 최단 거리가 가장 짧은 노드를 따로 안 구해도 된다.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

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())     # a번 노드에서 b번 노드로 가는 비용 c
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 거리는 0으로 설정하여, 큐에 삽입
    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])

앞서 나온 간단한 다익스트라 알고리즘에 비해 개선된 다익스트라 알고리즘은 시간 복잡도가 O(ElogV)로 훨씬 빠르다. 여기서 E는 간선의 개수, V는 노드의 개수이다. 시간 복잡도에 대해 조금 더 자세히 분석해보면 한 번 처리된 노드는 더 이상 처리되지 않기 때문에 큐에서 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 V번 이상 반복되지 않는다. 또한 V번 반복될 때마다 각각 자신과 연결된 간선들을 모두 확인하기 때문에 총 E번만큼 연산이 수행된다. 따라서 시간 복잡도는 O(ElogV)가 된다.

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)