다익스트라 알고리즘

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

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

• 처음 최단 거리 테이블은 무한으로 설정

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

다익스트라 성능 향상을 위해 우선순위 큐 자료구조 사용

우선순위 큐

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제
• 최소힙 : 값이 낮은 데이터부터
  최대힙 : 값이 높은 데이터부터
  파이썬은 기본적으로 최소힙이기 때문에 최대힙을 구현하고 싶다면 부호 바꾸어서 넣으면 된다.
  
  

💡 다익스트라와 우선순위 큐

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

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

  • +현재 가장 가까운 노드를 저장해놓기 위해 힙 자료구조 사용
  • 현재 거리가 가장 짧은 노드(최단거리)를 선택해야 하므로 최소힙을 사용

구현

import heapq

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드에 대한 정도 담는 리스트 초기화
# graph에 값 담을 때는 (end, cost)로
graph = [[] for _ in range(n+1)]
# 최단 거리 테이블 - 무한으로 초기화
dt = [INF]*(n+1)

def dks(start):
    # 시작 노드에 대해 초기화
    q = []
    heapq.heappush(q, (0, start)) # 출발노드. (거리, 노드)
    dt[start] = 0

    while q:
        # 가장 거리가 짧은 노드에 대한 정보 꺼내기
        cost, now = heapq.heappop(q)
        # 현재 꺼낸 값의 cost가 테이블에 기록된 값보다 크다면 이미 처리된 것이므로 무시
        if dt[now] < cost:
            continue
        # 현재 우선순위 큐에서 꺼낸 노드와 인접한 노드들을 확인
        for ad in graph[now]:
            # 현재 노드를 거쳐서 인접한 노드로 이동하는 거리가 테이블의 인접한 노드까지의 거리보다 짧은 경우
            c = cost + ad[1]
            if c < dt[ad[0]]:
                dt[ad[0]] = c
                heapq.heappush(q, (c, ad[0]))


dks(start)