こんにちは。
Dijkstra 法処理を行いました。その際に、priority queue 付きの Map
を作って用いると便利だろうと思い試しました1。
実行例
$ 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;
}
-
本当に便利であれば(他の用途は思いつきませんが)、計算量低減化も必要と思いました。 ↩