Dijkstra 法（priority 付き Map 利用, Javascript）

こんにちは。
Dijkstra 法処理を行いました。オリジナル形のように main 部が率直な形となるよう priority 付きの Map を作って用いました¹。

実行例

$ node dijkstra.js 
vertices of the graph: [Map Iterator] { 0, 1, 2, 3 }
source: 0
result: {path: [0, 2, 3], distance: 1.5}

ソース

dijkstra.js

const source = 0, destination = 3;

// array of edges represented by adjacent vertex and length
const diGraph = new Map([
  [0, [{target: 0, length: 0}, {target: 1, length: 1}, {target: 2, length: 0.5}, {target: 2, length: 1}]],
  [1, [{target: 2, length: 1}, {target: 1, length: 0}]],
  [2, [{target: 3, length: 1}, {target: 0, length: 0}]],
  [3, []]
]);

console.log("vertices of the graph:", diGraph.keys());
console.log("source:", source);
console.log("result:", dijkstra(source, destination, diGraph));

function dijkstra(source, destination, graph) {
  if (!graph.has(source)) return {path: [source], distance: 0};

  class MapWithPriority extends Map {
    constructor() {
      super();
      this.visited = new Set();
    }
    pop() {
      let keyMin, valueMin = Infinity;
      this.forEach((v, k) => {
        if (v < valueMin) {keyMin = k; valueMin = v;}
      });
      this.delete(keyMin);
      this.visited.add(keyMin);
      return [keyMin, valueMin];
    }
    set(key, value) {
      if (this.visited.has(key) || value >= this.get(key)) return false;
      super.set(key, value);
      return true;
    }
  }

  // initialization
  const prev = [];
  const pq = new MapWithPriority();
  pq.set(source, 0);
  let vertex, distance;

  // main
  while (pq.size > 0) {
    [vertex, distance] = pq.pop();
    if (vertex == destination) break;
    graph.get(vertex).forEach(edge => {
      if (pq.set(edge.target, distance + edge.length)) prev[edge.target] = vertex;;
    })
  }

  return {path: path(source, vertex), distance: distance}
  
  function path(source, vertex) {
  	const pathReversed = [vertex];
  	while (vertex !== source) {
  		vertex = prev[vertex];
  		pathReversed.push(vertex);
  	}
    return pathReversed.reverse();
  }
}

1. 本当に便利であれば（他の用途は思いつきませんが）、計算量低減化も今回のpop()部分に必要と思いました。参考例として、"Deep Dive into Data structures using Javascript - Priority Queue" (www.sahinarslan.tech) 。 ↩