User Tools

Site Tools


This is an old revision of the document!


λ Dijkstras

======= Algorithm ======= <syntax js> function dijkstra(source) { var distances = new Map(); var openQueue = new PriorityQueue(function(a,b) { return distances.get(a) - distances.get(b); }); // Add the `source` node with a distance of 0 to the sets. distances.set(source, 0); openQueue.enqueue(source); while (openQueue.length > 0) { // Pop the closest node from `openQueue`. var node = openQueue.dequeue(); var nodeDistance = distances.get(node); for (var i=0, c=node.edges.length; i<c; i++) { var newDistance = nodeDistance + node.edges[i].distance; var target = node.edges[i].target; if (!distances.has(target)) { // Enqueue a new node with `newDistance`. distances.set(target, newDistance); openQueue.enqueue(target); } else if (newDistance < distances.get(target)) { // Update the queue with a new priority for `target`. distances.set(target, newDistance); openQueue.update(target); } } } return distances; }</syntax> ======= Support ======= <syntax js> // Basic Map standin. function Map() { this.map = []; } Map.prototype = { get: function(x) { return this.map[x.hash]; }, set: function(x, v) { this.map[x.hash] = v; }, has: function(x, v) { return this.map.hasOwnProperty(x.hash); } }; // Basic PriorityQueue standin. function PriorityQueue(comparator) { this.comparator = comparator; this.data = []; } PriorityQueue.prototype = { enqueue: function(x) { this.data.push(x); this.data.sort(this.comparator); }, dequeue: function(x) { var result = this.data.shift(x); this.data.sort(this.comparator); return result; }, update: function(x) { this.data.sort(this.comparator); }, get length() { return this.data.length; } }; function run(graph) { result = dijkstra(graph); } </syntax> ======= Tests ======= <syntax js> function testA() { var nodeA = {hash:"A"}; var nodeB = {hash:"B"}; var nodeC = {hash:"C"}; var nodeD = {hash:"D"}; /* A--2---B |\ /| | \ 4 | 7 \/ 2 | /\ | | / 3 | |/ \| C---4--D */ nodeA.edges = [{target:nodeB, distance:2}, {target:nodeC, distance:7}, {target:nodeD, distance:3}]; nodeB.edges = [{target:nodeA, distance:2}, {target:nodeC, distance:4}, {target:nodeD, distance:2}]; nodeC.edges = [{target:nodeA, distance:7}, {target:nodeB, distance:4}, {target:nodeD, distance:4}]; nodeD.edges = [{target:nodeA, distance:3}, {target:nodeB, distance:2}, {target:nodeC, distance:4}]; var result = dijkstra(nodeA); assert(result.get(nodeA) === 0, "A->A = 0"); assert(result.get(nodeB) === 2, "A->B = 2"); assert(result.get(nodeC) === 6, "A->C = 6"); assert(result.get(nodeD) === 3, "A->D = 3"); } </syntax> ======= Options ======= <syntax js> { "title":"Dijkstras", "height":"430px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style type="text/css"> path { fill: #ddd; fill-opacity: .8; stroke: #fff; stroke-width: 1px; } circle { stroke-width: 1px; stroke: #444; } circle.current { stroke-width: 2px; r: 6; } circle.source { fill: red; } line { stroke: #999; } line.notused { stroke-dasharray: 5,5; } line.checking { stroke: black; stroke-width: 2px; } line.selected { stroke-width: 2px; } </style> <script src="http://d3js.org/d3.v3.min.js"></script> <script> var nodes = []; var links = []; var svg; function buildGraph() { svg = d3.select("body").append("svg:svg") .attr("width", 300) .attr("height", 350); newGraph(); } function newGraph() { nodes = []; links = []; var numNodes = 7+Math.floor(Math.random()*5); for (var i=0; i<numNodes; i++) { var node, isOK; do { node = [10+Math.random()*280, 30+Math.random()*280]; isOK = true; for (var j=0; j<nodes.length; j++) { var dx = node[0] - nodes[j][0], dy = node[1] - nodes[j][1]; if (dx * dx + dy * dy < 15*15) { isOK = false; break; } } } while (!isOK) node.edges = []; node.hash = "node:"+i; nodes.push(node); } var edge = function(a, b) { var dx = a[0] - b[0], dy = a[1] - b[1]; return { source: a, target: b, distance: Math.sqrt(dx * dx + dy * dy) }; } var hasEdge = function(a, b) { for (var i=0, c=links.length;i<c;i++) { if ((links[i].source === a && links[i].target === b) || (links[i].source === b && links[i].target === a)) return true; } return false; } d3.geom.delaunay(nodes).forEach(function(d) { if (!hasEdge(d[0], d[1])) links.push(edge(d[0], d[1])); if (!hasEdge(d[1], d[2])) links.push(edge(d[1], d[2])); if (!hasEdge(d[2], d[0])) links.push(edge(d[2], d[0])); }); // Remove a bunch of random edges. var toRemove = 2+Math.random()*numNodes/2; for (var i=0; i<toRemove; i++) { links.splice(Math.random()*(links.length-1), 1); } // Add all links to the nodes. links.forEach(function(l) { l.source.edges.push(l); var inverse = edge(l.target,l.source); inverse.inverse = l; l.target.edges.push(inverse); }); svg.selectAll("line").remove(); svg.selectAll("circle").remove(); var link = svg.selectAll("line").data(links); link.enter().append("svg:line"); link .attr("x1", function(d) { return d.source[0]; }) .attr("y1", function(d) { return d.source[1]; }) .attr("x2", function(d) { return d.target[0]; }) .attr("y2", function(d) { return d.target[1]; }); var node = svg.selectAll("g").data(nodes); node.enter() .append("circle") .attr("r", 4); node.attr("cx", function(d) { return d[0]; }) .attr("cy", function(d) { return d[1]; }); if (window.reset) reset(); } window.onload = buildGraph; function globals() { return {result:undefined}; } function args() { return nodes[0]; } function update(n, x, isRunning, duration, prev) { if (duration < 0) { return; // State-less visualisation. } var distances = x.lookupInScope("distances") || x.lookupInScope("result"); var sourceNode = x.lookupInScope("source"); // Update nodes. var circle = svg.selectAll("circle").data(nodes); if (distances) { circle.style("fill", function(d) { if (distances.has(d)) { return "hsl("+(distances.get(d)/3)+",100%,50%)"; } else if (d !== sourceNode) { return "black"; } }); } else { circle.style("fill", null); } // Highlight current node. var currentNode = x.lookupInScope("node"); circle.classed("current", function(d) {return d === currentNode;}); // Highlight source node. circle.classed("source", function(d) {return d === sourceNode;}); // Highlight current edge. var i = x.lookupInScope("i"); var link = svg.selectAll("line").data(links); link.classed("checking", function(d) { return (typeof i === "number" && currentNode && currentNode.edges.length > i) && (currentNode.edges[i] === d || currentNode.edges[i].inverse === d); }); } </script> </head> <body> <button onclick="newGraph()" style="position:absolute;left:0px;top:0px">New Graph</button> </body> </html> </syntax>

algorithm/dijkstras.1465683346.txt.gz · Last modified: 2016/06/11 15:15 by will