다익스트라 알고리즘(dijkstra algorithm)
* 최단 경로 구하기 알고리즘의 하나 - 다익스트라 알고리즘은, 특정한 노드에서 출발해 마지막 노드에 도착하는 것까지의 경로를 구하는 것과 관련 있다. - 관련 문제: 백준 10282번 - 해킹 (www.acmicpc.net/problem/10282) 백준 5719번 - 거의 최단 경로(www.acmicpc.net/problem/5719) import heapq mygraph = { 'A':{'B':8, 'C':1, 'D':2}, 'B':{}, 'C':{'B':5, 'D':2}, 'D':{'E':3, 'F':5}, 'E':{'F':1}, 'F':{'A':5} } def dijkstra(graph, start): # 초기화 distances = { node:float('inf') for node in gr..
2020. 10. 10.
최소 힙(min heap)의 구조를 가지고 있는 우선순위 큐 구현
import heapq queue = [] heapq.heappush(queue, [2, 'A']) heapq.heappush(queue, [5, 'B']) heapq.heappush(queue, [1, 'C']) heapq.heappush(queue, [7, 'D']) print(queue) """ [[1, 'C'], [5, 'B'], [2, 'A'], [7, 'D']] """ for x in range(len(queue)): print(heapq.heappop(queue)) """ [1, 'C'] [2, 'A'] [5, 'B'] [7, 'D'] """ - 출처 : FASTCAMPUS
2020. 10. 10.