다익스트라 알고리즘

얼마 전부터 다익스트라 알고리즘과 관련된 백준 문제를 풀기 시작했다. 다익스트라는 쉽게 말해 그래프에서 각 노드에 도달 할 수 있는 가장 작은 거리값을 찾는 방법이다. #다익스트라 기본형 1차원 def dijkstra(graph,start): INF = int(10e8) distance = [INF]*(n+1) distance[start] = 0 queue = [] heapq.heappush(queue,(0,start)) while queue: dist, now = heapq.heappop(queue) if distance[now] < dist: continue for now0,cost in graph[now]: dist0 = dist + cost if distance[now0] > dist0: distance[now0] = dist0 heapq.heappush(queue, (dist0, now0)) return distance 다익스트라 기본형 #다익스트라 기본형 2차원 def d...

원문링크 : 다익스트라 알고리즘