최단경로알고리즘

다익스트라(Dijkstra) 알고리즘 한 정점에서 다른 모든 정점으로 가는 최단거리를 구하는 알고리즘. 매번 방문하지 않은 노드 중 가장 가까운 노드를 선택하여 하나씩 최단 거리를 구해나간다. 다이나믹 프로그래밍, 그리디 알고리즘에 포함됨. 음의 가중치를 가진 간선을 포함할 수 없음. 음의 가중치를 간선이 있다면 벨만-포드 알고리즘 사용. import heapq graph = [[] for _ in range(v)] def dijkstra(start): distance = [int(1e9)] * (v) distance[start] = 0 q = [] heapq.heappush(q, (0, start)) while q: dist, now = heapq.heappop(q) if distance[now] < ..