최단 경로 ㅁ누제

각 간선의 가중치 합이 최소가 되는 두 정점 사이의 경로를 찾는 문제

다익스트라(Dijkstra)

노드 주변의 최단 경로만 택하는 대표적인 그리디 알고리즘 중 하나
노드 주변을 탐색할 때 BFS 사용
가중치가 음수인 경우에는 사용 불가능
heap과 같이 쓰임(우선순위 큐)
시간 복잡도 : O(ElogV)

# 예시
import heapq

def dijkstra(x):
	heap = []
    heapq.heappush(heap, (0, x))
    while heap:
    	weight, node = heapq.heappop(heap)
        if not visited[node]:
        	visited[node] = 1
            dist[node] = weight
            for new_n, new_w in arr[node]:
            	if not visited[new_n]:
                	heapq.heappush(heap, (new_w+weight, new_n))
            
inf = float('inf')
visited = [0] * N
dist = [inf] * N
dijkstra(0)