[알고리즘] 다익스트라(Dijkstra algorithm)와 우선순위 큐(MinHeap)

목 차 최소 힙 (MinHeap) 다익스트라 알고리즘 기본 개념 다익스트라 알고리즘 구현 최소 힙 (MinHeap) 다익스트라 알고리즘은 우선순위 큐(MinHeap)를 사용하는 것이 일반적이다. 최소 힙(MinHeap)의 정의 최소힙은 부모 노드가 자식 노드 보다 작거나 같은 값을 가지고 있는 이진 트리이다. 힙의 루트에는 트리에서 가장 작은 값이 위치한다. 최소 힙(MinHeap)의 연산 - 삽입: 새로운 요소를 힙의 마지막에 추가한 후, 부모 노드와 비교하며 위치를 조정하여 힙 속성을 만족시킨다. - 추출: 힙의 루트노드를 제거하고 마지막 노드를 루트로 이동시킨 다음, 자식들과 비교하며 위치를 조정하여 힙 속성을 만족시킨다. 여기서 추출할 때 JS 기준으로 shift() 메서드를 사용하면 앞에 노드를..

Algorithm 2023.11.14