다익스트라1 [python] dijkstra 알고리즘 dijkstra(다익스트라) 알고리즘은 source node로 부터 모든 node까지의 최단거리를 구하는 알고리즘이다. 먼저 다른 블로그에서 코드를 보고, 출력을 해보며 작동원리를 이해해보았다. 다익스트라 알고리즘을 구현하기전에 먼저 heapq에 대해 공부해야 했다. heapq는 우선순위큐 를 구현하기 위해 쓰이는 모듈이다. 따로 설치할 필요없이 import heapq 하면 된다. [heapq] 완전 이진 트리 형태 부모 노드 키값이 자식 노드 키값보다 항상 작다(최소힙) 키값의 대소관계는 부모/자식 관계에서만 성립하고, 자식끼리의 대소관계는 없다 heapq 예시 import heapq q = [] heapq.heappush(q, [2, 'D']) heapq.heappush(q, [8, 'B']) hea.. 2021. 3. 22. 이전 1 다음
