[Algorithm] 다익스트라 최단 경로 알고리즘

나동빈님의 서적 '이것이 취업을 위한 코딩테스트다'를 읽고 정리하였습니다.

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

다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

 

다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미한다. 현실 세계의 길은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어으 기본 알고리즘으로 채택되곤 한다.

 

원리

다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다.

매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다.

알고리즘의 원리는 아래와 같다.

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

이처럼, 다익스트라 최단 경로 알고리즘에서는 '방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택'하는 과정을 반복한다. 이렇게 선택된 노드는 '최단 거리'가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다.

다시 말해 다익스트라 알고리즘이 진행되면서 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.

 

구현

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

• 시간복잡도: O(V^2) (단, V는 노드의 개수)
  • 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형탐색
  • 현재 노드와 연결된 노드를 매번 일일이 확인
• 처음에 각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언
• 이후에 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해 매 단계마다 1차원 리스트의 모든 원소를 순차 탐색한다.

 

코드

import sys

input = sys.stdin.readline
# 무한을 의미하는 값으로 10억을 설정
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())
    # 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]
    # 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
    for _ 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):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

 

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

• 시간복잡도: O(ElogV) (단, V는 노드의 개수, E는 간선의 개수)
  • 최단 거리가 가장 짧은 노드를 단순히 선형적으로 찾는 것이 아닌 더욱더 빠르게 찾는 방법인 힙(Heap) 자료구조 사용
    • 힙 자료구조를 이용하면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다.
    • 이 과정에서 선형 시간이 아닌 로그시간이 걸린다.
  • 최대 E개의 간선 데이터를 힙에 넣었다가 다시 빼는 것으로 볼 수 있으므로 O(ElogE)
    • E는 항상 V^2보다 작으므로 간단히 O(ElogV)라고 볼 수 있다.

 

힙 설명

• 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나
  • 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제

  스택 - 가장 나중에 삽입된 데이터가 추출된다.
  큐 - 가장 먼저 삽입된 데이터가 추출된다.
  우선순위 큐(Priority Queue) - 가장 우선순위가 높은 데이터가 추출된다.

  • 우선순위 큐 구현 시 내부적으로 최소 힙(Min Heap) 또는 최대 힙(Max Heap)을 이용

  최소 힙 - 값이 낮은 데이터가 먼저 삭제
  최대 힙 - 값이 큰 데이터가 먼저 삭제
  
  최소 힙을 최대 힙처럼 사용하기 위해서 일부러 우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호(-)를 붙여서 원래의 값으로 돌리는 방식을 사용할 수 있다.

• 리스트와 삽입, 삭제 시간 비교
  • 리스트: 삽입 시간[O(1)], 삭제 시간[O(N)]
  • 힙(Heap): 삽입 시간[O(logN)], 삭제 시간[O(logN)]
• 힙 정렬
  • 데이터의 개수가 N개일 때, 힙 자료구조에 N개의 데이터를 모두 넣은 뒤에 다시 모든 데이터를 꺼낸다.
    • 시간 복잡도
      • 삽입할 때 O(logN)의 연산을 N번 반복하므로 O(NlogN)이고
      • 삭제할 때 O(logN)의 연산을 N번 반복하므로 O(NlogN)이다.
      • 따라서 전체 연산 횟수는 대략 2NlogN으로 시간 복잡도는 O(NlogN)이 된다.

 

코드

import heapq
import sys

input = sys.stdin.readline
# 무한을 의미하는 값으로 10억을 설정
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())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b, c))


def dijkstra(start):
    q = []
    # 시작 노드에 대해서 초기화
    heapq.heappush(q, (0, start))
    distance[start] = 0
    # 큐가 비어있지 않다면
    while q:
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시 - 노드의 개수 V만큼만 반복하도록
        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):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])