다익스트라 알고리즘
다익스트라 알고리즘은 어떤 그래프 G에 대해 i,j 노드를 잇는 최단 경로를 구하는 알고리즘이다.
그래프 자료구조는 실생활에서 가장 많이 접할 수 있으며 최단 경로를 구하는 행위는 자주 일어나기 때문에 상당히 중요하다.
해당 알고리즘을 공부하게 된 계기는 백준 - 1916 최소비용 구하기 문제를 풀다가 시간복잡도 문제에 허덕여 공부하게 되었다.
해당 개념은 이전 네트워크를 공부하며 라우팅 단계에서 접한적은 있지만 실제 코드로 구현해보는 것은 처음이기에 여러 블로그 자료들을 통해 공부하도록 하자 !
플로이드 - 워셜 알고리즘과의 차이점
나무위키상에서는 플로이드 - 워셜 알고리즘과 시간 복잡도가 동일하다고 나와있지만 실제로는 조금 달랐다.
플로이드 - 워셜 알고리즘은 그래프 상 모든 노드에 대해 모든 노드 간의 최단 경로 를 구하지만 다익스트라 알고리즘은 출발지로부터 도달 가능한 노드까지의 최단 경로 만을 구한다.
이에 데이터 개수가 매우 커지면 시간 복잡도 자체는 동일해질 수 있지만 실제 연산 횟수는 다익스트라 알고리즘이 더 적다.
다익스트라 알고리즘 개념 설명
note매우 길고 장황하게 적어놨었지만 시간이 지나고보니 코드가 너무 별로인거 같아서 다시 작성한다.
공부에 사용할 그래프
다익스트라 알고리즘에서 사용 할 자료구조를 풀기 전에 개념이 어떻게 흘러가는지 차례대로 생각해보자
위 예시에서 A 부터 F까지 가는 최단 경로를 구하고 싶다고 가정해보자
그렇다면 그 최단 경로는 A 부터 F 까지 바로 가거나, 어떤 노드를 경유하거나 두 가지중 하나이다.
이 때 경유하는 어떤 노드의 집합을 K 라고 정의해보자
이전에 풀이했던 플로이드 워셜 알고리즘에선 이 집합 K 는 그래프상의 모든 노드들이 존재했다면, 다익스트라 알고리즘은 출발지에서 도달 가능한 노드에 대해서만 존재한다.
그 이유는 플로이드 워셜 알고리즘의 관심사는 그래프 상에 존재하는 모든 간선들의 최단 경로였다면 다익스트라 알고리즘은 출발지에서 도착지까지의 최단 경로에만 관심이 있기 때문이다.
다익스트라 알고리즘은 다음과 같은 과정을 거친다.
- 그래프 상 경유지를 거치지 않고 어떤 그래프까지 가는 간선의 가중치를 담은 2차원 배열을 생성한다. (
weights) - 출발지로부터 도달 가능한 노드까지의 최단 경로를 담을 배열 (
shortestPath) 생성 (만약 도달이 불가능하다면 노드는 infinity로 설정) - 출발지로부터 도달 가능한 노드들을 담을 우선순위 큐 (
queue) 생성. 이 큐는shortestPath값이 작을 수록, 즉 가장 최단 경로인 노드를 우선적으로dequeue한다. - 최단 경로를 이미 구한 노드들을 표시할 배열을 생성한다. (
visited) queue에 출발지를 담고queue가 모두 빌 때 까지 5,6,7 과정을 반복한다.queue에서 값을 하나 뺀다.(currentNode) 이 값은 항상shortestPath에서 가장 값이 작은 노드가 반환된다. 이 값은 이미 최단 경로임이 보장되었으니visited[currentNode]를true로 표시한다.- 현재 있는 노드 (
currentNode) 와 인접한 (도달 가능한) 모든nextNode에 대해shortestPath[nextNode]값을 업데이트 한다. 이 값은 이전에 구해둔shortestPath[nextNode]와shortestPath[currentNode] + weights[currentNode][nextNode]중 최소 경로로 업데이트 된다. nextNode를queue에 담는다.
다익스트라 알고리즘을 다시 풀면서 느낀게 제일 중요한게 두가지 개념인거 같다.
하나는 출발지로부터 도달 가능한 노드에 대해서만 탐욕적으로 탐색 한다는 것, 두 번째는 우선순위 큐를 통해 반복 과정에서 큐에서 뽑은 노드가 매번 최단 경로가 이미 결정된 노드 라는 것이다.
해답 코드
밑 코드는 백준 - 1916 최소비용 구하기 에 대한 정답 코드이다.
// 입력
5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5
// 출력
4const fs = require("fs");
const path = require("path");
const filePath =
process.platform === "linux"
? "/dev/stdin"
: path.join(__dirname, "input.txt");
const inputs = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M] = inputs.slice(0, 2).map(Number);
const notes = inputs.slice(2, M + 2).map((line) => line.split(" ").map(Number));
const [start, end] = inputs[M + 2].split(" ").map(Number);
// N 개의 노드에서 W[i][j] 는 i 에서 j 까지 가는 간선의 가중치
const weights = Array.from({ length: N + 1 }, () =>
Array(N + 1).fill(Infinity)
);
notes.forEach(([start, end, weight]) => {
// 동일한 start 부터 end 까지 가는 간선이 여러개일 수 있으니
// 최소 가중치로 업데이트
weights[start][end] = Math.min(weights[start][end], weight);
});
for (let i = 1; i <= N; i++) {
// 자기 자신으로 가는 간선은 모두 0으로 초기화
weights[i][i] = 0;
}
// start 부터 N 개의 모든 노드까지 가는 최단 경로를 담을 배열
// 바텀업 과정을 통해 최단 경로로 업데이트 예정
const shortestPath = [...weights[start]];
// shortestPath 를 바라보는 우선순위 큐 객체 생성
const queue = {
queue: [],
size: 0,
enqueue(node) {
this.queue.push(node);
this.size++;
if (this.size === 1) {
return;
}
// min heap 성질을 만족하도록 정렬
let currentIndex = this.size - 1;
let parentIndex = Math.floor((currentIndex - 1) / 2);
while (
parentIndex >= 0 &&
shortestPath[this.queue[parentIndex]] >
shortestPath[this.queue[currentIndex]]
) {
const temp = this.queue[currentIndex];
this.queue[currentIndex] = this.queue[parentIndex];
this.queue[parentIndex] = temp;
currentIndex = parentIndex;
parentIndex = Math.floor((currentIndex - 1) / 2);
}
},
dequeue() {
if (this.size === 0) {
return null;
}
if (this.size === 1) {
this.size--;
return this.queue.pop();
}
const root = this.queue[0];
this.queue[0] = this.queue.pop();
this.size--;
// min heap 성질을 만족하도록 정렬
let currentIndex = 0;
let leftChildIndex = currentIndex * 2 + 1;
let rightChildIndex = currentIndex * 2 + 2;
while (true) {
let minIndex = currentIndex;
if (
shortestPath[this.queue[leftChildIndex]] <
shortestPath[this.queue[minIndex]]
) {
minIndex = leftChildIndex;
}
if (
shortestPath[this.queue[rightChildIndex]] <
shortestPath[this.queue[minIndex]]
) {
minIndex = rightChildIndex;
}
if (minIndex === currentIndex) {
break;
}
const temp = this.queue[currentIndex];
this.queue[currentIndex] = this.queue[minIndex];
this.queue[minIndex] = temp;
currentIndex = minIndex;
leftChildIndex = currentIndex * 2 + 1;
rightChildIndex = currentIndex * 2 + 2;
}
return root;
},
};
const visited = Array(N + 1).fill(false);
// queue 가 모두 빌 때 까지 shortestPath 업데이트
queue.enqueue(start);
while (queue.size > 0) {
const currentNode = queue.dequeue();
if (visited[currentNode]) {
continue;
}
visited[currentNode] = true;
// 다음에 방문할 노드들을 큐에 담는다.
for (let nextNode = 1; nextNode <= N; nextNode++) {
// 현재 노드와 인접하지 않은 노드는 고려하지 않는다.
if (weights[currentNode][nextNode] === Infinity) {
continue;
}
// 이미 방문한 노드는 고려하지 않는다.
if (visited[nextNode]) {
continue;
}
// start 노드부터 nextNode 까지 가는 최단 경로를 업데이트
shortestPath[nextNode] = Math.min(
shortestPath[nextNode],
shortestPath[currentNode] + weights[currentNode][nextNode]
);
queue.enqueue(nextNode);
}
}
console.log(shortestPath[end]); // 4회고
다익스트라 알고리즘을 이해하는데도 애를 먹었는데 우선순위 큐를 구현하는데도 애를 꽤나 먹었다.
갸갸갹 너무 헷갈려