다익스트라 알고리즘 구현 (python)

다익스트라 알고리즘 (Dijkstra Algorithm)

 -특정 노드에서 출발하여 다른 모든 노드까지 갈 수 있는 최단경로를 계산

 -매 상황에서 가장 비용이 적게 드는 노드를 선택하는 과정을 반복한다 (그리디임)

 -모든 간선의 가중치가 양수일 때 정상적으로 동작한다

---

구현 방법

  1) 최단거리 테이블을 초기화한다. (출발노드는 0, 나머지는 INF)

  2) 현재 노드와 인접하고 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택

  3) 2에서 선택한 노드를 거쳐 다른 노드로 가는 비용을 계산, 최단거리 테이블을 갱신

  4) 2,3번 과정 반복

---

현재 노드로부터 최단거리가 가장 짧은 노드 선택하기

간단하게 인접한 노드를 매번 모두 순회하는 방법을 떠올릴 수 있다.

 그러나 선형탐색으로 최단거리가 짧은 노드를 선택하게 되면 시간복잡도가 O(n^2)으로,

 입력받은 노드 개수가 매우 많다면(예를 들면, 1만 개 이상) 시간초과가 날 것이다.

 

따라서 선형탐색 대신, 우선순위큐를 이용하도록 한다!

 우선순위큐 구현에 사용하는 자료구조 중 하나는 힙인데,

 힙은 삽입 또는 삭제시 O(logN)의 시간복잡도를 가지게 되므로 연산수행시간을 크게 줄일 수 있다.

 참고로, 파이썬에서 기본으로 제공하는 heapq 라이브러리는 최소힙으로 구현된다.

 

---

파이썬 코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) #매우 큰 숫자인 10억을 무한대로 정의한다

#n(노드 수), m(간선 수), x(출발노드) 입력받기
n,m = map(int,input().split())
x = int(input())

#간선 정보를 저장할 리스트
graph = [[] for i in range(n+1)]
#최단거리 정보를 저장할 리스트 (초기값은 전부 무한대로 초기화)
distance = [INF]*(n+1)

#간선 정보 입력받기 (a에서 b 노드로 가는 비용이 c)
for _ in range(m):
	a,b,c = map(int,input().split())
    graph[a].append((b,c))
    
   
def dijkstra(start):
	q=[]
    heapq.heappush(q,(0,start)) # 우선순위큐에 시작노드와 그 최단경로 정보를 삽입
    distance[start]=0 #출발노드 자기자신까지의 거리는 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(x)

#각 노드별로 최단경로 출력
for i in range(1,n+1):
	if distance[i]==INF:
    	print("도달할 수 없음")
    else:
    	print(distance[i])