자바스크립트로 보는 다익스트라

다익스트라 알고리즘이란?

현재까지 가장 가까운 정점을 하나씩 확정해가며 시작점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이다.

다익스트라는 언제 사용하는가

• 그래프에서 한 출발점 → 모든 정점까지 최단 거리를 구해야 할 때
• 가중치가 음수가 아니고 가중치가 서로 다를 때

가중치가 음수가 아니어야 하는 이유

다익스트라는 가장 가까운 정점부터 최단 거리를 구해 나가면 결과적으로 모든 경로에 대해 최단 거리를 모두 구할 수 있을 것이라는 것을 가정하기 때문에 그리디 알고리즘에 해당한다.
이러한 가정이 성립하려면 가중치가 음수여서는 안 된다. 가중치가 음수일 경우 현재 선택한 최단 거리보다 더 적은 거리가 나중에 나올 수도 있기 때문이다.

다익스트라와 BFS의 차이

항목	BFS	다익스트라
자료구조	Queue	Priority Queue
거리 배열	-1	Infinity
방문 기준	한 번만	여러 번 가능
갱신 조건	처음 방문	더 짧으면 갱신
간선 가중치	모두 동일	서로 다름
핵심 연산	dist + 1	dist + weight

다익스트라는 어떻게 구현하는가

가장 가까운 정점부터 꺼내야 하기 때문에 자료구조로 최소힙을 이용한다.
시작 정점외에 모든 거리를 Infinity로 둔다.
최소힙에 [노드, 거리] 형태로 시작 정점을 먼저 push한다.
최소힙이 빌 때까지 가장 가까운 정점부터 꺼내어 다음 노드까지의 최소 거리를 갱신한다.

class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(item) {
    this.heap.push(item);
    this._up();
  }

  _up() {
    let i = this.heap.length - 1;
    while (i > 0) {
      let p = Math.floor((i - 1) / 2);
      if (this.heap[p][1] <= this.heap[i][1]) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }

  pop() {
    if (this.heap.length === 1) return this.heap.pop();
    const top = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._down();
    return top;
  }

  _down() {
    let i = 0;
    const n = this.heap.length;
    while (true) {
      let l = i * 2 + 1;
      let r = i * 2 + 2;
      let s = i;

      if (l < n && this.heap[l][1] < this.heap[s][1]) s = l;
      if (r < n && this.heap[r][1] < this.heap[s][1]) s = r;
      if (s === i) break;

      [this.heap[i], this.heap[s]] = [this.heap[s], this.heap[i]];
      i = s;
    }
  }

  isEmpty() {
    return this.heap.length === 0;
  }
}

function dijkstra(N, graph, start) {
  const dist = Array(N).fill(Infinity);
  dist[start] = 0;

  const pq = new MinHeap();
  pq.push([start, 0]);

  while (!pq.isEmpty()) {
    const [cur, curDist] = pq.pop();

    if (curDist > dist[cur]) continue;

    for (const [next, weight] of graph[cur]) {
      if (dist[next] > curDist + weight) {
        dist[next] = curDist + weight;
        pq.push([next, dist[next]]);
      }
    }
  }

  return dist;
}

[백준] 최소 비용구하기

• 난이도 : 골드 5
• 문제 링크 : https://www.acmicpc.net/problem/1916

경로 간 비용이 다르므로 BFS를 이용할 수 없고 다익스트라 알고리즘을 이용해야 한다.
주어진 값들을 이용해 그래프를 만들고 시작 노드와 종료 노드를 변수에 저장한다.
자료구조로 최소 힙을 구현하고, 다익스트라 알고리즘을 구현한다.
종료 지점의 거리를 반환한다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const N = +input[0];
const M = +input[1];
const graph = Array.from({ length: N + 1 }, () => []);

for (let i = 2; i < M + 2; i++) {
  const [start, end, cost] = input[i].split(" ").map(Number);
  graph[start].push([end, cost]);
}

const [start, end] = input[M + 2].split(" ").map(Number);

class MinHeap {
  constructor() {
    this.heap = [];
  }

  isEmpty() {
    return this.heap.length === 0;
  }

  push(val) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.heap.length - 1;
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      if (this.heap[idx][1] > this.heap[parentIdx][1]) break;
      [this.heap[idx], this.heap[parentIdx]] = [
        this.heap[parentIdx],
        this.heap[idx],
      ];
      idx = parentIdx;
    }
  }

  pop() {
    if (this.heap.length === 1) return this.heap.pop();
    let val = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return val;
  }

  bubbleDown() {
    let idx = 0;
    let n = this.heap.length;

    while (true) {
      let leftChild = idx * 2 + 1;
      let rightChild = idx * 2 + 2;
      let smallest = idx;

      if (leftChild < n && this.heap[leftChild][1] < this.heap[smallest][1])
        smallest = leftChild;
      if (rightChild < n && this.heap[rightChild[1]] < this.heap[smallest][1])
        smallest = rightChild;
      if (smallest === idx) break;

      [this.heap[smallest], this.heap[idx]] = [
        this.heap[idx],
        this.heap[smallest],
      ];
      idx = smallest;
    }
  }
}

function dijkstra(N, graph, start) {
  const dist = Array(N + 1).fill(Infinity);
  dist[start] = 0;

  const pq = new MinHeap();
  pq.push([start, 0]);

  while (!pq.isEmpty()) {
    const [cur, curWeight] = pq.pop();

    if (dist[cur] < curWeight) continue;

    for (let [next, weight] of graph[cur]) {
      if (dist[next] > curWeight + weight) {
        dist[next] = curWeight + weight;
        pq.push([next, dist[next]]);
      }
    }
  }

  return dist;
}

const distance = dijkstra(N, graph, start);

console.log(distance[end]);

[백준] 최단 경로

• 난이도 : 골드 4
• 문제 링크 : https://www.acmicpc.net/problem/1753

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const [V, E] = input[0].split(" ").map(Number);
const K = +input[1];
const graph = Array.from({ length: V + 1 }, () => []);

for (let i = 2; i < E + 2; i++) {
  const [start, end, cost] = input[i].split(" ").map(Number);
  graph[start].push([end, cost]);
}

class MinHeap {
  constructor() {
    this.heap = [];
  }

  isEmpty() {
    return this.heap.length === 0;
  }

  push(val) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.heap.length - 1;
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      if (this.heap[idx][1] > this.heap[parentIdx][1]) break;
      [this.heap[idx], this.heap[parentIdx]] = [
        this.heap[parentIdx],
        this.heap[idx],
      ];
      idx = parentIdx;
    }
  }

  pop() {
    if (this.heap.length === 1) return this.heap.pop();
    let val = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return val;
  }

  bubbleDown() {
    let idx = 0;
    let n = this.heap.length;

    while (true) {
      let leftChild = idx * 2 + 1;
      let rightChild = idx * 2 + 2;
      let smallest = idx;

      if (leftChild < n && this.heap[leftChild][1] < this.heap[smallest][1])
        smallest = leftChild;
      if (rightChild < n && this.heap[rightChild][1] < this.heap[smallest][1])
        smallest = rightChild;
      if (smallest === idx) break;

      [this.heap[smallest], this.heap[idx]] = [
        this.heap[idx],
        this.heap[smallest],
      ];
      idx = smallest;
    }
  }
}

function dijkstra(N, graph, start) {
  const dist = Array(N + 1).fill(Infinity);
  dist[start] = 0;

  const pq = new MinHeap();
  pq.push([start, 0]);

  while (!pq.isEmpty()) {
    const [cur, curWeight] = pq.pop();

    if (dist[cur] < curWeight) continue;

    for (let [next, weight] of graph[cur]) {
      if (dist[next] > curWeight + weight) {
        dist[next] = curWeight + weight;
        pq.push([next, dist[next]]);
      }
    }
  }

  return dist;
}

const distance = dijkstra(V, graph, K);
const answer = [];

for (let i = 1; i < distance.length; i++) {
  answer.push(distance[i] === Infinity ? "INF" : distance[i]);
}

console.log(answer.join("\n"));

[백준] 파티

• 난이도 : 골드 3
• 문제 링크 : https://www.acmicpc.net/problem/1238

위의 문제들과 다르게 특정 노드로 가는 비용이 아닌 왕복 비용이 가장 큰 경우를 구해야 한다.
위의 풀이들에서는 특정 노드에서 원래 노드로 돌아가는 비용은 구할 수 있지만, 각 노드에서 특정 노드까지 가는 비용은 구할 수 없다.
각 노드에서 가는 비용을 구하기 위해 1번 노드부터 N번 노드까지 반복문을 돌며 다익스트라를 반복하면 시간 효율성이 떨어지므로 발상의 전환이 필요하다.
다익스트라는 한 지점에서 다른 모든 지점까지의 최단 거리를 구하는 것이므로 엣지 방향을 반대로 한 그래프에서 다익스트라를 실행하면 각 지점에서 특정 지점까지의 최단 거리를 한 번에 구할 수 있다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const [N, M, X] = input[0].split(" ").map(Number); // 노드, 엣지, 도착점
const graph = Array.from({ length: N + 1 }, () => []);
const reverse_graph = Array.from({ length: N + 1 }, () => []);

for (let i = 1; i < M + 1; i++) {
  const [start, end, cost] = input[i].split(" ").map(Number);
  graph[start].push([end, cost]);
  reverse_graph[end].push([start, cost]);
}

class MinHeap {
  constructor() {
    this.heap = [];
  }

  isEmpty() {
    return this.heap.length === 0;
  }

  push(val) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.heap.length - 1;
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      if (this.heap[idx][1] > this.heap[parentIdx][1]) break;
      [this.heap[idx], this.heap[parentIdx]] = [
        this.heap[parentIdx],
        this.heap[idx],
      ];
      idx = parentIdx;
    }
  }

  pop() {
    if (this.heap.length === 1) return this.heap.pop();
    let val = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return val;
  }

  bubbleDown() {
    let idx = 0;
    let n = this.heap.length;

    while (true) {
      let leftChild = idx * 2 + 1;
      let rightChild = idx * 2 + 2;
      let smallest = idx;

      if (leftChild < n && this.heap[leftChild][1] < this.heap[smallest][1])
        smallest = leftChild;
      if (rightChild < n && this.heap[rightChild][1] < this.heap[smallest][1])
        smallest = rightChild;
      if (smallest === idx) break;

      [this.heap[smallest], this.heap[idx]] = [
        this.heap[idx],
        this.heap[smallest],
      ];
      idx = smallest;
    }
  }
}

function dijkstra(N, graph, start) {
  const dist = Array(N + 1).fill(Infinity);
  dist[start] = 0;

  const pq = new MinHeap();
  pq.push([start, 0]);

  while (!pq.isEmpty()) {
    const [cur, curWeight] = pq.pop();

    if (dist[cur] < curWeight) continue;

    for (let [next, weight] of graph[cur]) {
      if (dist[next] > curWeight + weight) {
        dist[next] = curWeight + weight;
        pq.push([next, dist[next]]);
      }
    }
  }

  return dist;
}

const distance_go = dijkstra(N, reverse_graph, X); // 가는 비용
const distance_back = dijkstra(N, graph, X); // 오는 비용
let max_distance = 0;

for (let i = 1; i <= N; i++) {
  if (distance_go[i] + distance_back[i] > max_distance)
    max_distance = distance_go[i] + distance_back[i];
}

console.log(max_distance);