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

 

 

출처: https://youtu.be/acqm9mM1P6o

- 나동빈 이코테

 

 

 

 

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

# n: 노드, m: 간선
n, m = 6, 5

# start: 시작 노드
start = 1

# graph: 연결되어 있는 노드 정보 리스트
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))

graph = [
  [],
  [(2, 2), (4, 1)],
  [(4, 2), (3, 3)],
  [(2, 3), (6,5)],
  [(3, 3), (5, 1)],
  [(3, 1), (6, 2)],
  []
]

# 방문하지 않은 노드 중 가장 최단 거리가 짧은 노드를 반환
def get_shortest(d, v):
  min_value = INF
  index = 0
  for i in range(1, n + 1):
    if d[i] < min_value and not v[i]:
      min_value = d[i]
      index = i
  return index

def dijkstra(s):
  # 시작 노드 초기화
  distance[s] = 0
  visited[s] = True
  for j in graph[s]:
    distance[j[0]] = j[1]
  # 시작 노드를 제외한 전체 n - 1 개의 노드에 대해 반복
  for i in range(n - 1):
    # 현재 최단 거리가 가장 짧은 노드를 꺼내 방문 처리
    now  = get_shortest(distance, visited)
    visited[now] = True
    # 현재 노드와 연결된 다른 노드 확인
    for j in graph[now]:
      cost = distance[now] + j[1]
      # 현재 노드를 거쳐 다른 노드를 이동하는 거리가 더 짧은 경우
      if cost < distance[j[0]]:
        distance[j[0]] = cost


# dijkstra algorithm 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
  # 도달할 수 없는 경우 무한(INF) 출력
  if distance[i] == INF:
    print("INF")
  else:
    print(distance[i])

 

 

 

 

 

최소 힙은 값이 가장 낮은 값부터 꺼냄

최대 힙은 값이 가장 높은 값부터 꺼냄

 

 

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)

 

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)

 

 

 

 

 

 

heap 을 이용하여 개선된 다익스트라 알고리즘

 

 

import heapq

INF = int(1e9)

# n: 노드, m: 간선
n, m = 6, 5

# start: 시작 노드
start = 1

# 각 노드와 연결되어 있는 리스트
graph = [
  [],
  [(2, 2), (4, 1), (3, 5)],
  [(4, 2), (3, 3)],
  [(2, 3), (6, 5)],
  [(3, 3), (5, 1)],
  [(3, 1), (6, 2)],
  []
]

# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

def dijkstra(s):
  q = []
  # 시작 노드로 가기 위한 최단 경로는 0으로 설정, q에 삽입
  heapq.heappush(q, (0, s))
  # 시작 노드 초기화
  distance[s] = 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("INF")
  else:
    print(distance[i])