Dijkstra1 [알고리즘] 다익스트라 알고리즘 정의 특정한 정점으로부터 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다. 음의 간선은 포함시킬 수 없다. 활용 현실 생활에서 많이 사용되는 알고리즘으로 인공위성 GPS 등이 있다. 코드 시간 복잡도 O(N * log N)를 가지는 코드이다. import heapq import math def dijkstra(graph, start): distances = {node : math.inf for node in graph} distances[start] = 0 queue = [] heapq.heappush(queue, [distances[start], start]) while queue: curr_distance, curr_dest = heapq.heappop(queue) if distances[c.. 2021. 10. 24. 이전 1 다음 728x90 반응형