다익스트라 - 파이썬

다익스트라는 최단 경로 문제에서 사용되는 알고리즘이고 방향과 가중치가 존재하는 그래프에서 사용한다
여기에서 가중치는 모두 양수여야한다
기본적인 수행 방식은 다음과 같다

수행 방식
1. 방문 여부를 체크하는 배열과 최단 거리를 기록하는 배열 두 개를 선언하고, 시작 노드의 최단 거리를 0으로 초기화하고 나머지 노드들의 최단 거리를 무한대로 초기화한다.
2. 시작 노드에서 인접한 노드들의 최단거리를 갱신한다(시작 노드 -> 인접 노드의 가중치)
3. 시작 노드와 연결된 노드들 중 방문하지 않았으면서 거리가 최소인 노드를 선택한다.
4. 선택한 노드와 인접한 노드들의 최단 거리를 갱신한다 -> 기존에 기록되어있던 거리와 현재 경로에서의 거리를 비교
5. 방문하지 않은 노드들 중 거리값이 최소인 노드를 선택해 4,5번을 반복한다.

다익스트라 알고리즘은 두 가지 방식으로 구현할 수 있는데 앞서 설명한대로 리스트를 두 개를 선언해 순회하는 방식과 최소 heap 자료구조를 사용하는 방식이 있다
리스트를 두 개를 선언하는 경우에는 계속해서 모든 노드($V$)를 순회하면서 최소 노드를 찾아야하기 때문에 시간복잡도가 $O(V^2)$ 이다

이를 개선하기 위해서 최소 heap 자료구조를 활용할 수 있다.
최소 힙의 경우에는 최소값이 힙의 맨 앞/위에 위치하기 때문에 최소 노드를 찾기 위해 리스트를 순회할 필요가 없다

리스트 두 개를 사용하는 경우(기본)

import sys

inf = float("inf")
n, m = map(int, sys.stdin.readline().split()) # n: 노드 수, m: 에지 수
start = int(sys.stdin.readline()) # 시작 노드

graph = [[] for _ in range(n+1)]
visited = [False] * (n+1) # 방문 리스트
dist = [inf] * (n+1) # 거리 리스트

for _ in range(m): # 그래프 초기화
	v, u, w = map(int, sys.stdin.readline().split())
    graph[v].append((u,w))
 
def find_smallest_node(): # 거리가 최소인 노드 찾기 
	min_val = inf
    min_idx = 0
    for i in range(1,n+1):
    	if not visited[i] and dist[i] < min_val:
        	min_val = dist[i]
            min_idx = i
    return min_idx

def dijkstra(start):
	dist[start] = 0
    visited[start] = True
    
    for u, w in graph[start]:
    	dist[u] = w
    
    for _ in range(n-1):
    	v = find_smallest_node()
        visited[v] = True
        
        for u, w in graph[v]:
            dist[u] = min(dist[u], dist[v] + w)

dijkstra(start)

최소 heap을 사용하는 경우

import sys, heapq

inf = float("inf")
n, m = map(int, sys.stdin.readline().split()) # n: 노드 수, m: 에지 수
start = int(sys.stdin.readline()) # 시작 노드

graph = [[] for _ in range(n+1)]
dist = [inf] * (n+1) # 거리 리스트

for _ in range(m): # 그래프 초기화
	v, u, w = map(int, sys.stdin.readline().split())
    graph[v].append((u,w))
    
def dijkstra(start):
	q = []
    heapq.heappush(q, (0, start)) # 거리를 기준으로 정렬할 수 있도록 거리를 0번째 위치에 두기
    dist[start] = 0
    
    while q:
    	w1, v = heapq.heappop(q)
        
        for u, w2 in graph[v]:
        	cost = dist[v] + w2
        	if dist[u] > cost:
            	dist[u] = cost
                heapq.heappush(q, (cost, u))
dijkstra(start)

이렇게 최소힙을 사용해 구현한 다익스트라 알고리즘은 $O(ElogV)$의 시간복잡도를 갖는다
힙에서 최소 노드를 pop한 후 나머지 노드들을 heap으로 만드는 데에 $logV$의 시간이 걸리고, 이러한 과정을 그래프에 연결된 모든 에지마다 수행하기 때문이다