7. 최단 경로 알고리즘

📌 1. 우선순위 큐와 힙

1. 우선순위 큐(Priority Queue)

• 우선순위가 높은 데이터가 먼저 나가는 자료구조

• 일반적으로, 힙(Heap)을 이용해 구현

2. 힙(Heap)

• 우선순위 큐를 구현하기 위해 사용되는 완전이진트리 형태의 자료구조

• 최소 힙 (Min Heap) & 최대 힙 (Max Heap)

• 원소의 삽입, 삭제에 대해 O(logN)의 시간 복잡도를 가짐 (Why? 트리 구조니까!)

🎨 Min Heap - 오름차순 정렬

(Python의 heapq 라이브러리는 기본적으로 Min Heap만 지원)

import heapq

array = [2, 6, 3, 1, 5, 7, 4, 8, 9]
h = []
result = []

for i in array:
  heapq.heappush(h, i)

for _ in range(len(h)):
  result.append(heapq.heappop(h))

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

🎨 Max Heap - 내림차순 정렬

import heapq

array = [2, 6, 3, 1, 5, 7, 4, 8, 9]
h = []
result = []

for i in array:
  heapq.heappush(h, -i) # 넣을 때 -

for _ in range(len(h)):
  result.append(-heapq.heappop(h)) # 뺄 때 -

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

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

• 특정한 노드 -> 모든 노드까지의 최단 경로

• 음의 간선이 없을 때 적용 가능

• 기본적으로, 최단 경로를 구하는 문제는 DP로 분류됨. 거기에 더해서, 다익스트라 알고리즘은 그리디 알고리즘으로 분류되기도 함.

  • B/C 매 단계마다 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 때문.

  • 참고로, 위의 '방문하지 않은 노드 중 최단 거리가 가장 짧은 노드'를 선택하기 위해 힙 자료구조 사용

• 힙 자료구조를 사용하는 경우, 시간 복잡도는 O(ElogV)

  • E : 간선의 개수, V : 노드의 개수

🎨 구현 코드 - graph는 인접 리스트 방식

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

# n : 노드의 개수, m : 간선의 개수
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 : 비용
  a, b, c = map(int, input().split())
  graph[a].append((b, c))

def dijkstra(start):
  q = [] # 우선순위 큐
  # 시작 노드 먼저 처리
  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])

📌 3. 플로이드 워셜 알고리즘

• 모든 노드 -> 모든 노드까지의 최단 경로

• 매 노드마다, 그 노드를 거쳐가는 경로의 거리 계산

  • 점화식 : [a에서 b까지의 거리] = min([a에서 b까지의 거리], [a에서 k까지의 거리 + k에서 b까지의 거리])

• 시간 복잡도 : O(N3) (N: 노드의 개수)

🎨 구현 코드 - graph는 인접 행렬 방식

INF = int(1e9)

# n : 노드의 개수, m : 간선의 개수
n, m = map(int, input().split())
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신부터 자기 자신까지의 거리는 0으로 초기화
for a in range(1, n + 1):
  for b in range(1, n + 1):
    if a == b:
      graph[a][b] = 0
      
# 간선 정보 입력받기
for _ in range(m):
  # a : 출발 노드, b : 도착 노드, c : 비용
  a, b, c = map(int, input().split())
  graph[a][b] = c

for i in range(1, n + 1): # 각 노드에 대해
  for a in range(1, n + 1):
    for b in range(1, n + 1):
      graph[a][b] = min(graph[a][b], graph[a][i] + graph[i][b])

for a in range(1, n + 1):
  for b in range(1, n + 1):
    if graph[a][b] == INF:
      print("INFINITY", end = ' ')
    else:
      print(graph[a][b], end= ' ')
  print()

---

무향 그래프는 [출발 지점: a, 도착 지점: b], [출발 지점: b, 도착 지점: a] 이 두 경우 모두를 graph에 넣어줘야 함

---

[참고]

• (이코테 2021 강의 몰아보기) 7. 최단 경로 알고리즘 (https://www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7)