다익스트라 알고리즘

다익스트라 알고리즘은 어떤 그래프 G에 대해 i,j 노드를 잇는 최단 경로를 구하는 알고리즘이다.

그래프 자료구조는 실생활에서 가장 많이 접할 수 있으며 최단 경로를 구하는 행위는 자주 일어나기 때문에 상당히 중요하다.

해당 알고리즘을 공부하게 된 계기는 백준 - 1916 최소비용 구하기 문제를 풀다가 시간복잡도 문제에 허덕여 공부하게 되었다.

해당 개념은 이전 네트워크를 공부하며 라우팅 단계에서 접한적은 있지만 실제 코드로 구현해보는 것은 처음이기에 여러 블로그 자료들을 통해 공부하도록 하자 !

플로이드 - 워셜 알고리즘과의 차이점

나무위키상에서는 플로이드 - 워셜 알고리즘과 시간 복잡도가 동일하다고 나와있지만 실제로는 조금 달랐다.

플로이드 - 워셜 알고리즘은 그래프 상 모든 노드에 대해 모든 노드 간의 최단 경로 를 구하지만 다익스트라 알고리즘은 출발지로부터 도달 가능한 노드까지의 최단 경로 만을 구한다.

이에 데이터 개수가 매우 커지면 시간 복잡도 자체는 동일해질 수 있지만 실제 연산 횟수는 다익스트라 알고리즘이 더 적다.

다익스트라 알고리즘 개념 설명

매우 길고 장황하게 적어놨었지만 시간이 지나고보니 코드가 너무 별로인거 같아서 다시 작성한다.

공부에 사용할 그래프

다익스트라 알고리즘에서 사용 할 자료구조를 풀기 전에 개념이 어떻게 흘러가는지 차례대로 생각해보자

위 예시에서 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 최소비용 구하기 에 대한 정답 코드이다.

예제 입 출력

다익스트라 알고리즘

const 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

회고

다익스트라 알고리즘을 이해하는데도 애를 먹었는데 우선순위 큐를 구현하는데도 애를 꽤나 먹었다.

갸갸갹 너무 헷갈려