JavaScriptでダイクストラ法

前置き

AtCoderでダイクストラ法の典型問題が出されたのを機に
jsでダイクストラ法を学習したので記事にする

D - Super Takahashi Bros.
5分で解説動画

目次

・前提知識
・ダイクストラ法について
・ループ法
・優先度付きキュー
・解説動画を参考に関数化したもの　完成形
・あとがき

前提知識

・幅優先探索
・優先度付きキュー(Priority Queue)

ダイクストラ法について

最短経路問題を解くためのアルゴリズム

始点を決めたら
次の移動先候補の中で最もコストの低い点を決定
その点までの移動コストを確定させる
その点の次の移動可能先を候補に加えて最もコストの低い点を決定
その点までの移動コストを確定させる
以下繰り返し

詳しい解説 ダイクストラ法（最短経路問題）

ループ法

こちらの方の記事を参考に実装してみた
提出結果　結果はTLE
2220 ms

移動先候補の中から最もコストの低い値をループして探すので
計算量はO(N^2)

優先度付きキュー

最もコストの低い順に整列させるため優先度付きキュー(Prority Queue)を使用
計算量はO(NlogN)
また、構造体？のような情報は不要なので点とコストの情報をキューに詰め込むように修正
提出結果　結果はAC
784 ms

解説動画を参考に関数化したもの完成形

解説動画を参考に情報を簡素化し関数化した
点とコストの情報は隣接リストに変更した
Prority Queueの先頭要素にコストを入れるようにした(先頭要素を比較するように修正)
Main関数の外に関数を定義しdistを返すようにした（これは私の好み）

function Main(input) {
  input = input.split("\n");
  let [N] = input[0].split(' ').map(e => Number(e))

  let Graph = [...Array(N)].map(() => [])

  for (let i = 0; i < N - 1; i++) {
    let [a, b, x] = input[i + 1].split(' ').map(e => Number(e))
    x--
    Graph[i].push([i + 1, a])
    Graph[i].push([x, b])
  }

  let distance = dijkstra(0, Graph, N)
  console.log(distance[N - 1]);

  return
}

function dijkstra(startV, Graph, N) {
  let dist = Array(N).fill(Number.MAX_SAFE_INTEGER)
  dist[startV] = 0
  
  let pq = new PriorityQueue()
  pq.enqueue([0, startV])

  while (!pq.empty()) {
    let [c, v] = pq.dequeue()
    if (dist[v] < c) continue
    for (let i = 0; i < Graph[v].length; i++) {
      let [to, cost] = Graph[v][i]
      if (dist[to] > dist[v] + cost) {
        dist[to] = dist[v] + cost;
        pq.enqueue([dist[to], to])
      }
    }
  }

  return dist
}


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

  enqueue(item) {
    let heap = this.heap;
    let i = heap.length++;
    let j;

    while (i) {
      j = Math.floor((i - 1) / 2);
      if (heap[j][0] <= item[0]) break;
      heap[i] = heap[j]
      i = j;
    }

    heap[i] = item;
  }

  dequeue() {
    let heap = this.heap;
    let top = heap[0];
    let popped = heap.pop();

    let i = 0;
    let k = Math.floor(heap.length / 2);
    let j;

    while (i < k) {
      j = (i * 2) + 1;
      if (heap[j + 1] !== undefined) {
        if (heap[j + 1][0] < heap[j][0]) ++j;
      }

      if (popped[0] <= heap[j][0]) break;

      heap[i] = heap[j];

      i = j;
    }

    if (heap.length) {
      heap[i] = popped;
    }

    return top;
  }

  empty() {
    return this.heap.length === 0
  }

  get size() {
    return this.heap.length;
  }

  get top() {
    return this.heap[0];
  }
}

提出結果　結果はAC
626 ms

あとがき

ちなみにC++の回答は100ms以下もざらにある

記事執筆時点でのjsでACした回答者は私を含め5人
（数が少ないので目視で確認）
それに対してC++でACした提出数は
187*20+2=3742件
（１ページが20件で、順繰りにページ遷移をしていたが８ページ程で終わりが見えそうにないのでやめようと思ったがURLのクエリパラメーターにpageがあることに気づき、page=100表示される、page=200表示されない、page=150表示される...で特定、二分探索ってこんなところで役に立つんですね、ちなみにpythonは884件）

同一回答者による複数投稿が含まれるので実際の回答者数はもう少し下がるが、jsとは比較にならない
jsでダイクストラ法を解説した記事が少ないし、そもそも競プロをjsでやるのが間違いな気もするが行けるところまで行こうと思う