[최단 경로] 최단 경로 알고리즘 (2) 다익스트라 알고리즘

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

• 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
• '음의 간선' 즉, 0보다 작은 값을 가지는 간선이 없을 때 정상적으로 동작
• 기본적으로 그리디 알고리즘
  • 매번 가장 비용이 적은 노드를 선택
• 알고리즘 동작 원리
  1. 출발 노드를 설정한다
  2. 최단 거리 테이블을 초기화한다
  3. 방문하지 않은 노드들 중에서 최단 거리가 가장 짧은 노드를 선택한다
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산한 후, 기존 비용과 비교하여 더 작은 값으로 최단 거리 테이블을 갱신한다
  5. 3번과 4번 과정을 반복한다
• 항상 '각 노드에 대한 현재까지의 최단 거리' 정보를 1차원 리스트인 최단 거리 테이블에 저장하며 리스트를 계속 갱신함
• 2가지 구현 방법 존재
  1. 구현하기 쉽지만 느리게 동작하는 코드
  2. 구현하기 까다롭지만 빠르게 동작하는 코드 = 개선된 다익스트라 알고리즘 ⬅️ 특히 방법 2를 숙지하기!

첫 번째 구현 방법

• 시간복잡도는 O(V^2)
  • 이때, V는 노드의 개수
  • 노드 개수가 10,000개를 넘어가는 문제라면 시간이 너무 오래 걸려서  문제를 해결하기 어려움
•  소스코드 설명
  • 입력 데이터 수가 많다는 가정하에 input()을 sys.stdin.realine()으로 치환하여 사용하는 방법 적용
  • 모든 리스트는 (노드의 개수 + 1)로 할당하여, 노드의 번호를 인덱스로 사용해서 바로 리스트에 접근하도록 함
    • 그래프를 표현할 때 자주 사용하는 표현 방법 
  • '무한'이라는 값을 표현하기 위해서 int(1e9)를 사용함. 10억과 같은 의미
    • 이 외에도 999,999,999 나 987,654,321을 사용할 수 있음
  • 각 노드에대한 최단 거리를 담는 2차원 리스트 distance 선언
  • get_shortest_node() 함수
    • 단계마다 '방문하지 않은 노드 중에서 최단 거리가 짧은 노드를 선택'하기 위해 distance 리스트의 모든 원소를 확인(순차 탐색) 
• 소스코드

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_shortest_node():
  min_value = INF
  idx = 0
  for i in range(1, n + 1):
    if min_value > distance[i] and not visited[i]:
      min_value = distance[i]
      idx = i
  return idx

# 다익스트라
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_shortest_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])

• 입력 예시

6 11 1 1 2 2 1 3 5 1 4 1 2 3 3 2 4 2 3 2 2 3 6 5 4 3 3 4 5 1 5 3 1 5 6 2

• 출력 예시

0 2 3 1 2 4

✅ 두 번째 구현 방법 - 개선된 다익스트라 알고리즘

• 최악의 경우에도 시간 복잡도는 O(ElogV)
  • 이때, V는 노드 개수 & E는 간선 개수
• 앞선 다익스트라 알고리즘은 '최단 거리가 가장 짧은 노드'를 찾기 위해 매번 선형 탐색을 수행함
• 힙 자료구조를 사용하여 이러한 시간 단축 가능
  • 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로터 가장 거리가 짧은 노드를 빠르게 찾을 수 있음
  • 힙 자료구조는 우선순위 큐 구현에 사용
    • 우선순위 큐: 우선순위가 가장 높은 데이터를 가장 먼저 삭제
    • 데이터를 우선순위에 따라 처리할 수 있음
  • 파이썬에서는 heapq를 사용하여 우선순위 큐 구현 가능
    • 우선순위 큐에 데이터 묶음을 넣으면, 항상 첫 번째 원소를 기준으로 우선순위를 설정
    • ex) (거리, 노드)를 넣으면 '거리'를 기준으로 우선순위 설정
  • 최소 힙과 최대 힙
    • 최소 힙: 값이 낮은 데이터가 먼저 삭제
    • 최대 힙: 값이 큰 데이터가 먼저 삭제
    • 파이썬 라이브러리에서는 기본적으로 최소 힙 채택
    • 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선하여 방문하므로 최소힙 그대로 사용
    • 최소힙을 최대힙으로 바꾸기 위해서는 힙에 넣기 전과 후에 데이터 값에 음수 부호를 붙여주면 됨
  • 최소 힙으로 구현한 우선순위 큐를 이용하여 시작 노드로부터 거리가 짧은 노드 순서대로 큐에서 나올 수 있도록 다익스트라 알고리즘을 작성하면 됨
• 소스코드
  • 앞선 코드와 달리 get_shortest_node() 함수를 작성할 필요 없음
    • 최단 거리가 가장 짧은 노드를 선택하는 과정을 우선순위 큐로 대체하였기 때문.
  • 최단 거리를 저장하기 위한 distance 리스트 사용

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

# 노드의 개수, 간선의 개수 입력받기
n, m = map(int, input().split())
# 시작 노드 번호 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기
graph = [[] for _ 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 = []
  # 시작 노드로 가기 위한 최단 경로는 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: # 도달할 수 없는 경우 INF 출력
    print("INF")
  else: # 도달할 수 있는 경우 거리 력
    print(distance[i])

• 우선순위 큐를 필요로 하는 다른 문제 유형에도 위 유형을 흡사하게 적용 가능