[알고리즘] 최단거리 구하기, 다익스트라 알고리즘

● 자료구조 우선순위 큐

 

- 자료 중 최소 or 최대 값을 먼저 출력한다. (기본적으로 최소)

 

- 라이브러리 heapq를 사용한다.

 

- 입력(heapq.heappush(list, value), 출력(heapq.heappop(list))

 

 

● 다익스트라 알고리즘 (시작 지점부터 최단거리를 구하는 알고리즘)

 

1. 경로가 가장 짧은 노드 부터 탐색

 

2. 최단 거리 list를 무한으로 설정한다.

 

3. 노드 중에서 가장 짧은 거리를 갖고 있는 노드를 방문한다.

 

4. 현재 노드와 연결된 노드들의 거리를 계산하고 최단거리 list를 갱신한다.

 

5. 3,4를 반복한다. 모든 노드를 방문할 때까지

 

그래프

최단거리 정보/ 시작시 무한으로 설정한다.

1번 노드에서 다음노드까지 거리 갱신 // 가장 짧은 4번 노드를 방문하여 연결된 노드의 최단거리 갱신

위 과정을 반복한 후 나온 결과

● 코드로 구현

import heapq

graph = [[] for _ in range(n+1)] # 각 노드가 연결된 정보(다음노드,거리)

inf = int(1e9)
distance = [inf]*(n+1) # 최단거리 정보 처음엔 무한으로 설정

def dijkstra(start):
  q = [] # 우선순위 큐로 사용할 리스트
  
  heapq.heappush(q,(0,start)) # 시작 노드 입력
  
  distance[start] = 0 # 거리정보 갱신
  
  while q:
    dist, now = heapq.heappop(q) # 가장 짧은 경로 노드 방문
    
    if distance[now] < dist:
      continue
    
    for n,d in graph[now]:
      cost = dist + d
      
      if cost < distance[n]:
        distance[n] = cost
        heapq.heappush(q,(cost,n))