[백준][다익스트라] 1753 최단 경로 NodeJs 구현

목차

https://www.acmicpc.net/problem/1753

문제

 

문제 구현 방향

전형적인 다익스트라 알고리즘이다. 아래 블로그를 참고해서 운선순위 큐를 구현하고 풀었다.

https://velog.io/@717lumos/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘] 다익스트라(Dijkstra) 알고리즘

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

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

  getMin() {
    return this.heap[1];
  }

  getSize() {
    return this.heap.length - 1;
  }

  isEmpty() {
    return this.heap.length < 2;
  }

  insert(node) {
    let current = this.heap.length;

    while (current > 1) {
      const parent = Math.floor(current / 2);
      if (this.heap[parent][0] > node[0]) {
        this.heap[current] = this.heap[parent];
        current = parent;
      } else break;
    }

    this.heap[current] = node;
  }

  remove() {
    let min = this.heap[1];

    if (this.heap.length > 2) {
      this.heap[1] = this.heap[this.heap.length - 1];
      this.heap.splice(this.heap.length - 1);

      let current = 1;
      let leftChildIndex = current * 2;
      let rightChildIndex = current * 2 + 1;

      while (this.heap[leftChildIndex]) {
        let childIndexToCompare = leftChildIndex;
        if (
          this.heap[rightChildIndex] &&
          this.heap[rightChildIndex][0] < this.heap[childIndexToCompare][0]
        )
          childIndexToCompare = rightChildIndex;

        if (this.heap[current][0] > this.heap[childIndexToCompare][0]) {
          [this.heap[current], this.heap[childIndexToCompare]] = [
            this.heap[childIndexToCompare],
            this.heap[current],
          ];
          current = childIndexToCompare;
        } else break;

        leftChildIndex = current * 2;
        rightChildIndex = current * 2 + 1;
      }
    } else if (this.heap.length === 2) {
      this.heap.splice(1, 1);
    } else {
      return null;
    }

    return min;
  }
}
let INF = 9999999999;
function dijkstra(start, V, graph) {
  let dist = Array(V + 1).fill(INF);
  let pq = new MinHeap();
  dist[start] = 0;
  pq.insert([0, start]);
  while (pq.getSize()) {
    let [c_dist, c_node] = pq.remove();
    for (let [n_node, n_dist] of graph[c_node]) {
      let t_dist = n_dist + c_dist;
      if (t_dist < dist[n_node]) {
        dist[n_node] = t_dist;
        pq.insert([t_dist, n_node]);
      }
    }
  }
  return dist;
}

let adjV = Array.from({ length: 2000001 }, () => []);

let [V, E] = input[0].trim().split(" ").map(Number);
let s = +input[1];

for (let i = 2; i < input.length; i++) {
  let ar = input[i].trim().split(" ").map(Number);
  adjV[ar[0]].push(ar.slice(1));
}
let ans = dijkstra(s, V, adjV);
for (let i = 1; i < ans.length; i++) {
  if (ans[i] === INF) console.log("INF");
  else console.log(ans[i]);
}