# Differences

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

 algorithm:dijkstras [2016/05/23 23:44]will algorithm:dijkstras [2016/06/28 22:59] (current)will Fix showing incorrect highlighted edge. Both sides previous 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 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 6: Line 6: function dijkstra(source) { function dijkstra(source) { var distances = new Map(); var distances = new Map(); - var openQueue = new PriorityQueue(function(a,​b) {return distances.get(a) - distances.get(b);​});​ + 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); distances.set(source,​ 0); openQueue.enqueue(source);​ openQueue.enqueue(source);​ ​ ​ while (openQueue.length > 0) { while (openQueue.length > 0) { - var u = openQueue.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​ }​ Line 64: Line 73: return result; return result; }, }, - ​sort: function() { + ​update: function(x) { this.data.sort(this.comparator);​ this.data.sort(this.comparator);​ - } + ​}, - };​ + get length() { + return this.data.length;​ + } + }; + + function run(graph) { + result = dijkstra(graph);​ + } + ​ ======= Tests ======= ======= Tests ======= Line 75: Line 92: var nodeB = {hash:"​B"​};​ var nodeB = {hash:"​B"​};​ var nodeC = {hash:"​C"​};​ var nodeC = {hash:"​C"​};​ + var nodeD = {hash:"​D"​};​ ​ ​ - nodeA.edges = [{target:​nodeB,​ distance:20}, {target:​nodeC,​ distance:70}]; + ​ - nodeB.edges = [{target:​nodeA,​ distance:20}, {target:​nodeC,​ distance:40}]; + /*  A--2---B - nodeC.edges = [{target:​nodeA,​ distance:70}, {target:​nodeB,​ distance:40}]; + |\    /| + | \  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);​ var result = dijkstra(nodeA);​ - assert(result.get(nodeA) === 0); + assert(result.get(nodeA) === 0, "​A->​A = 0"); - assert(result.get(nodeB) === 20); + assert(result.get(nodeB) === 2, "​A->​B = 2"); - assert(result.get(nodeC) === 60); + assert(result.get(nodeC) === 6, "​A->​C = 6"); + assert(result.get(nodeD) === 3, "​A->​D = 3"); } } ​ Line 91: Line 122: { { "​title":"​Dijkstras",​ "​title":"​Dijkstras",​ - "​height":"​250px" + "​height":"​430px" } } ​ Line 99: Line 130: <​html>​ <​html>​ <​head>​ <​head>​ +