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

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

実行例

$ node dijkstra.js 
vertices of the graph: [Map Iterator] { 0, 1, 2, 3 }
source: 0
result: Map(4) { 0 => 0, 2 => 0.5, 1 => 1, 3 => 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: 1}, {target: 2, length: 0.5}]],
  [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) {
  class MapWithPriorityQueue extends Map {
    constructor() {
      super();
      this.visited = new Map();
    }
    pop() {
      let key = undefined, valueMinimum = Infinity;
      if (this.size > 0) {
        this.forEach((p, k) => {
          if (p < valueMinimum) {key = k; valueMinimum = p;}
        });
        this.delete(key);
        this.visited.set(key, valueMinimum);
      }
      return [key, valueMinimum];
    }
    set(key, value) {
      if (this.visited.has(key) || value >= this.get(key)) return;
      super.set(key, value);
    }
    getVisited() {
      return this.visited;
    }
  }

  // initialization              
  const pq = new MapWithPriorityQueue();
  pq.set(source, 0);

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

  return pq.getVisited();
}

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