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); }); distances.set(source, 0); openQueue.enqueue(source); while (openQueue.length > 0) { var node = openQueue.dequeue(); for (var i=0, c=node.edges.length; i<c; i++) { var newDistance = distances.get(node) + 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)) { distances.set(target, newDistance); openQueue.sort(); // Resort the priority queue. } } } 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; }, sort: function() { this.data.sort(this.comparator); }, get length() { return this.data.length; } };</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":"360px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <script> /* Optional functions function globals() { return {}; } function args() { return null; } */ function update(n, x, isRunning, duration, prev) { if (duration < 0) { return; // State-less visualisation. } var out = x.lookupInScope("out"); document.body.innerHTML = "out = "+JSON.stringify(out); } </script> </head> <body> </body> </html> </syntax>

algorithm/dijkstras.1464073516.txt.gz · Last modified: 2016/05/24 00:05 by will