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

최단경로 알고리즘

- 가장 짧은 경로를 찾는 알고리즘

- 다양한 문제 상황들

 

1 ) 한 지점에서 다른 한 지점까지의 최단경로

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

3 ) 모든 지점에서 다른 모든 지점까지의 최단경로

 

- 각 지점은 그래프에서 노드로 표현

- 지점 간 연결된 도로는 그래프에서 간선으로 표현

다익스트라 최단 경로

- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로

- 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작

- 현실 세계의 도로(간선)은 음의 간선으로 표현 X

 

- 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류(다이나믹 프로그래밍 원리도 이용됨)

- 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정 반복

 

다익스트라 최단 경로 알고리즘 동작 과정

 

1. 출발 노드 설정

2. 최단 거리 테이블 초기화 (자기 자신은 0으로 설정)

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산 -> 최단 거리 테이블 갱신

5. 위의 3번/4번 과정 반복 수행

- 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있음

- 처리 과정에서 더 짧은 경로를 찾으면 다음부터는 이 경로가 짧은 경로로 갱신

다익스트라 알고리즘 : 동작 과정

[초기단계] 그래프를 준비하고 출발 노드 설정

[1단계] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 1번 노드 처리 -> 2번, 3번, 4번 노드 갱신

[2단계] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 4번 노드 처리 -> 3번, 5번 노드 갱신

[3단계] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 2번 노드 처리 -> 갱신이 이루어지지 X

[4단계] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 5번 노드 처리 -> 3번, 6번 노드 갱신

[5단계] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 3번 노드 처리 -> 갱신이 이루어지지 X

[6단계] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 6번 노드 처리 -> 마지막 노드(간선 존재X) -> 갱신X

다익스트라 특징

- 그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드 선택 -> 임의의 과정 반복

- 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 X

- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해

- 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보 저장

다익스트라 알고리즘 : 간단한 구현

- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인(순차 탐색)

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)]
# 방문한 적이 있는지 체크하는 목적의 리스트
visited = [False] * (n+1)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)

# 모든 간선 정보를 입력받기
for i 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 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], end=' ')

다익스트라 알고리즘 : 간단한 구현 성능 분석

- 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 함

- 전체 시간 복잡도 = O(V^2)

- 코딩 테스트의 최단 경로 문제는 전체 노드 개수가 5,000개 이하라면 이 코드로 문제 해결 가능

- BUT 10,000개 넘어가는 경우 문제 해결에 어려움이 있음

우선순위 큐(Priority Queue)

- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

- 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인하는 경우 -> 우선순위 큐 이용

- 파이썬, C++, JAVA를 포함한 대부분은 프로그래밍 언어에서 표준 라이브러리 형태로 지원함

 

+ ) 스택은 가장 나중에 삽입 데이터가, 큐는 가장 먼저 삽입된 데이터가, 우선순위 큐는 가장 우선순위가 높은 데이터가 가장 먼저 추출된다. 

우선순위 큐(Priority Queue) - 힙(Heap)

- 우선순위 큐를 구현하기 위해 사용하는 자료구조

- 최소 힙(Min heap - 값이 낮은 데이터부터 추출)과 최대 힙(Max heap - 값이 높은 데이터부터 추출)이 있음 

- 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용

- 퀵 정렬, 병합 정렬과 같은 시간 복잡도를 가짐 (최악의 경우에도 O(logN) 시간 보장

# 최소 힙
import heapq

# 오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
  h = []
  result = []
  # 모든 원소를 차례대로 힙에 삽입
  for value in iterable:
    heapq.heappush(h, value)
  # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
  for i in range(len(h)):
    result.append(heapq.heappop(h))
  return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

# 결과 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 최대 힙
import heapq

# 오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
  h = []
  result = []
  # 모든 원소를 차례대로 힙에 삽입
  for value in iterable:
    heapq.heappush(h, -value)
  # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
  for i in range(len(h)):
    result.append(-heapq.heappop(h))
  return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

# 결과 -> [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

다익스트라 알고리즘 : 개선된 구현 방법

- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙(Heap) 자료구조 이용

- 다익스트라 알고리즘이 동작하는 기본 원리는 동일

- 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가적으로 이용하는 것이 차이점

- 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소힙을 사용

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

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

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

def dijkstra(start):
  q = []
  # 시작 노드로 가기 위한 최단 경로는 0으로 설정, 큐에 삽입
  distance[start] = 0
  heapq.heappush(q, (0, start))
  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], end=' ')

다익스트라 알고리즘 : 개선된 구현 방법 성능

- 힙 자료구조 이용 다익스트라 알고리즘 시간 복잡도 : O(ElogV)

- 노드를 하나씩 꺼내서 검사하는 반복문 while문은 노드의 개수 N이상의 횟수로 처리되지 X

- 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총횟수는 최대 간선의 개수(E)만큼 연산 수행

- 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사

- 시간 복잡도 : O(ElogE)로 판단할 수 있음 -> 중복 간선을 포함하지 않는 경우 -> O(ElogV)