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

  목  차

• 최소 힙 (MinHeap)
• 다익스트라 알고리즘 기본 개념
• 다익스트라 알고리즘 구현

 

 

---

 

  최소 힙 (MinHeap)

 

다익스트라 알고리즘은 우선순위 큐(MinHeap)를 사용하는 것이 일반적이다. 

 

 

최소 힙(MinHeap)의 정의

 

최소힙은 부모 노드가 자식 노드 보다 작거나 같은 값을 가지고 있는 이진 트리이다. 힙의 루트에는 트리에서 가장 작은 값이 위치한다.

 

 

최소 힙(MinHeap)의 연산

 

- 삽입: 새로운 요소를 힙의 마지막에 추가한 후, 부모 노드와 비교하며 위치를 조정하여 힙 속성을 만족시킨다.

 

- 추출: 힙의 루트노드를 제거하고 마지막 노드를 루트로 이동시킨 다음, 자식들과 비교하며 위치를 조정하여 힙 속성을 만족시킨다.

 

 

여기서 추출할 때 JS 기준으로 shift() 메서드를 사용하면 앞에 노드를 추출하고 제거한 다음 남은 노드들의 위치를 하나씩 앞으로 이동시키므로 비효율적이다. 이런 물리적 삭제 보다는 논리적 삭제 개념을 활용하는 편이 효율적이다. 

 

논리적 삭제는 루트노드를 다른 변수에 저장하고, 마지막 노드를 루트노드에 저장하고 배열의 길이를 줄이는 방식으로 한다.

 

 

---

 

  다익스트라 알고리즘 기본 개념

 

이 알고리즘은 주로 가중치(weight)가 있는 그래프에서 사용된다. 한 노드에서 다른 노드로 가는 데 필요한 비용이나 거리를 나타낸다.

 

흔히 인공위성 GPS 소프트웨어에서 사용된다.

 

 

다익스트라 알고리즘의 특징

 

1. 양의 가중치: 모든 노드의 가중치가 양수일 때만 정확한 결과를 보장한다.
2. 최적의 선택: 항상 가장 작은 비용을 가진 노드를 선택한다.
3. 경로 추적: 각 최단 경로에서 자신의 이전 노드에 대한 정보를 저장하여 경로 추적을 할 수 있다.

 

 

---

 

  다익스트라 알고리즘 구현

 

1. 출발점 설정: 출발점 부터 각 노드까지의 최소 비용(Weight)을 저장한다.
2. 최소 비용 노드 탐색: 아직 처리되지 않은 노드 중에서 최소 비용을 가진 노드를 찾고 방문한다.
3. 경로 가중치 업데이트: 현재 경로가 기존의 경로보다 작은 값일 경우, 그 노드까지의 비용을 업데이트 한다.

위 과정을 반복한다.

 

 

다익스트라 예시 코드

 

const graph = [
	[],  // 사용 안 함.
	[
		{to: 2, dist: 5},
		{to: 3, dist: 4}
	],
	[
		{to: 1, dist: 5},
		{to: 6, dist: 11},
		{to: 3, dist: 5}
	],
	[
		{to: 1, dist: 4},
		{to: 2, dist: 5},
		{to: 4, dist: 8},
		{to: 5, dist: 5}
	],
	[
		{to: 3, dist: 8},
		{to: 5, dist: 6},
		{to: 6, dist: 3}
	],
	[
		{to: 3, dist: 5},
		{to: 4, dist: 6},
		{to: 6, dist: 9}
	],
	[
		{to: 2, dist: 11},
		{to: 4, dist: 3},
		{to: 5, dist: 9},
	]
]

const endPoint = 6;

const distArray = [0, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]
const parentArray = [0, 1, 2, 3, 4, 5, 6]
const isVisited = [true, false, false, false, false, false, false]

const pq = new MinHeap({ to: 1, dist: 0 });

while(pq.queue.length){

	const {to, dist} = pq.pop();

	if(to == null) break;
  if(isVisited[to]) continue;

	isVisited[to] = true;
	if(to == endPoint){
		console.log(dist);
        break;
	}
			
for(let el of graph[to]){
	if(isVisited[el.to]) continue;
	const newDist = el.dist + dist;
	if(newDist < distArray[el.to]){
		distArray[el.to] = newDist;
		pq.insert({ to: el.to, dist: newDist });
	}
};
	
	

}