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

こんにちは。
Dijkstra 法処理を行いました。その際に、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 distance
const directedGraph = new Map([
  [0, [{target: 0, distance: 0}, {target: 1, distance: 1}, {target: 2, distance: 1}, {target: 2, distance: 0.5}]],
  [1, [{target: 2, distance: 1}, {target: 1, distance: 0}]],
  [2, [{target: 3, distance: 1}, {target: 0, distance: 0}]],
  [3, []]
]);

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

function dijkstra(source, destination, graph) {
  class MapWithPriorityQueue extends Map {
    popEntry() {
      let key = undefined, valueMinimum = Infinity;
      if (this.size > 0) {
        this.forEach((p, k) => {
          if (p < valueMinimum) {key = k; valueMinimum = p;}
        });
        this.delete(key);
      }
      return [key, valueMinimum];
    }
  }

  // initialization              
  const visitedVertices = new Map();  // store their distanceTotal for result
  const shortestCandidates = new MapWithPriorityQueue();
  shortestCandidates.set(source, 0);

  // main
  while (shortestCandidates.size > 0) {
    const [vertex, distanceTotal] = shortestCandidates.popEntry();
    visitedVertices.set(vertex, distanceTotal);
    if (vertex == destination) break;
    graph.get(vertex).forEach((edge, i) => {
      const successor = edge.target;
      if (visitedVertices.has(successor)) return;
      const distanceTotalCandidate = distanceTotal + edge.distance;
      if (!shortestCandidates.has(successor) || distanceTotalCandidate < shortestCandidates.get(successor)) {
        shortestCandidates.set(successor, distanceTotalCandidate);
      }
    })
  }

  return visitedVertices;
}

1. 本当に便利であれば（他の用途は思いつきませんが）、計算量低減化も必要と思いました。 ↩