# Differences

This shows you the differences between two versions of the page.

 algorithm:dijkstras [2016/05/23 23:22]will in progress algorithm:dijkstras [2016/06/28 22:59] (current)will Fix showing incorrect highlighted edge. 2016/06/28 22:59 will Fix showing incorrect highlighted edge.2016/06/11 15:26 will Always highlight source node.2016/06/11 15:15 will Working viz2016/05/24 00:05 will Working code.2016/05/23 23:44 will 2016/05/23 23:22 will in progress Next revision Previous revision 2016/06/28 22:59 will Fix showing incorrect highlighted edge.2016/06/11 15:26 will Always highlight source node.2016/06/11 15:15 will Working viz2016/05/24 00:05 will Working code.2016/05/23 23:44 will 2016/05/23 23:22 will in progress Line 4: Line 4: ======= Algorithm ======= ======= Algorithm ======= - function dijkstra(graph, ​source) { + function dijkstra(source) { - var openSet ​= new PriorityQueue();​ + var distances = new Map(); + var openQueue ​= new PriorityQueue(function(a,​b) { + return distances.get(a) - distances.get(b);​ + }); ​ ​ - source.distance ​= 0; + ​// Add the source node with a distance ​of 0 to the sets. - ​openSet.enqueue(source);​ + distances.set(source, ​0); + ​openQueue.enqueue(source);​ ​ ​ - while (openSet.length > 0) { + while (openQueue.length > 0) { - var u = openSet.dequeue(); + // Pop the closest node from openQueue. + var node = openQueue.dequeue(); + var nodeDistance = distances.get(node); ​ ​ - for (var i=0, c=u.edges.count; i​ - ​6 ​         dist[v] ← INFINITY ​                 // Unknown distance from source to v + - ​7 ​         prev[v] ← UNDEFINED ​                // Previous node in optimal path from source + - ​8 ​         add v to Q                          // All nodes initially in Q (unvisited nodes) + - 9 + - 10      dist[source] ← 0                        // Distance from source to source + - 11 + - 12      while Q is not empty: + - 13          u ← vertex in Q with min dist[u] ​   // Source node will be selected first + - 14          remove u from Q + - 15 + - 16          for each neighbor v of u:           // where v is still in Q. + - 17              alt ← dist[u] + length(u, v) + - 18              if alt < dist[v]: ​              // A shorter path to v has been found + - 19                  dist[v] ← alt + - 20                  prev[v] ← u + - 21 + - 22      ​return ​dist[], prev[] + - ​ + ======= Support ======= ======= Support ======= - /* Support code... + // Basic Map standin. - function run(args) { + 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);​ } } - */ ​ ======= Tests ======= ======= Tests ======= - /* Unit tests… function testA() { function testA() { - ​if (!ok) { + ​var nodeA = {hash:"​A"​};​ - ​throw "Not ok." + 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"); } } - */ ​ Line 67: Line 122: { { "​title":"​Dijkstras",​ "​title":"​Dijkstras",​ - "​height":"​250px" + "​height":"​430px" } } ​ Line 75: Line 130: <​html>​ <​html>​ <​head>​ <​head>​ +