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 u = openQueue.dequeue(); for (var i=0, c=u.edges.count; i<c; i++) { var newDistance = distances.get(u) + u.edges[i].distance; var target = u.edges.target; if (!distances.has(target)) { distances.set(target, newDistance); openSet.enqueue(target); } else if (newDistance < distances.get(target)) { distances.set(target, newDistance); openSet.sort(); } } } }</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); } };</syntax> ======= Tests ======= <syntax js> function testA() { var nodeA = {hash:"A"}; var nodeB = {hash:"B"}; var nodeC = {hash:"C"}; nodeA.edges = [{target:nodeB, distance:20}, {target:nodeC, distance:70}]; nodeB.edges = [{target:nodeA, distance:20}, {target:nodeC, distance:40}]; nodeC.edges = [{target:nodeA, distance:70}, {target:nodeB, distance:40}]; var result = dijkstra(nodeA); assert(result.get(nodeA) === 0); assert(result.get(nodeB) === 20); assert(result.get(nodeC) === 60); } </syntax> ======= Options ======= <syntax js> { "title":"Dijkstras", "height":"250px" } </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.1464072262.txt.gz · Last modified: 2016/05/23 23:44 by will