User Tools

Site Tools


Differences

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

Link to this comparison view

Next revision
Previous revision
algorithm:dijkstras [2016/05/23 23:22]
will in progress
algorithm:dijkstras [2016/06/28 22:59] (current)
will Fix showing incorrect highlighted edge.
Line 4: Line 4:
 ======= Algorithm ======= ======= Algorithm =======
 <syntax js> <syntax js>
-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 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<c; i++) { +        for (var i=0, c=node.edges.length; i<c; i++) { 
-            var newDistance = u.distance ​u.edges[i].distance;​ +            var newDistance = nodeDistance ​node.edges[i].distance;​ 
-            var target = u.edges.target;​ +            var target = node.edges[i].target; 
-            if (newDistance ​target.distance) { +            if (!distances.has(target)) { 
-                target.distance = newDistance;​ +                // Enqueue a new node with `newDistance`. 
-                ​openSet.sort();+                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);
             }             }
         }         }
     }     }
     ​     ​
- 4 +    ​return ​distances; 
- ​5 ​     for each vertex v in Graph: ​            // Initialization +}</​syntax>​
- ​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[] +
-</​syntax>​+
  
 ======= Support ======= ======= Support =======
 <syntax js> <syntax js>
-/* 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);​
 } }
-*/ 
 </​syntax>​ </​syntax>​
  
 ======= Tests ======= ======= Tests =======
 <syntax js> <syntax js>
-/* 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");
 } }
-*/ 
 </​syntax>​ </​syntax>​
  
Line 67: Line 122:
 { {
     "​title":"​Dijkstras",​     "​title":"​Dijkstras",​
-    "​height":"​250px"+    "​height":"​430px"
 } }
 </​syntax>​ </​syntax>​
Line 75: Line 130:
 <​html>​ <​html>​
 <​head>​ <​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>​ <​script>​
-/* Optional functions+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() { function globals() {
-    return {};+    return {result:​undefined};
 } }
 function args() { function args() {
-    return ​null;+    return ​nodes[0];
 } }
-*/ 
  
 function update(n, x, isRunning, duration, prev) { function update(n, x, isRunning, duration, prev) {
Line 90: Line 272:
         return; // State-less visualisation.         return; // State-less visualisation.
     }     }
-    var out = x.lookupInScope("​out"); +    ​ 
-    ​document.body.innerHTML ​= "out = "+JSON.stringify(out);+    ​var distances ​= x.lookupInScope("​distances"​) || x.lookupInScope("​result"); 
 +    ​var sourceNode = x.lookupInScope("​source"​) || nodes[0]; 
 +     
 +    // 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 inInnerLoop = n && n.lineno >= 17 && n.lineno <= 28; 
 +    var link = svg.selectAll("​line"​).data(links);​ 
 +    link.classed("​checking",​ function(d) { 
 +        return (typeof i === "​number"​ && inInnerLoop && currentNode && currentNode.edges.length > i) &&​ 
 +            (currentNode.edges[i] === d || currentNode.edges[i].inverse === d); 
 +    });
 } }
 </​script>​ </​script>​
 </​head>​ </​head>​
 <​body>​ <​body>​
 +<button onclick="​newGraph()"​ style="​position:​absolute;​left:​0px;​top:​0px">​New Graph</​button>​
 </​body>​ </​body>​
 </​html>​ </​html>​
 </​syntax>​ </​syntax>​
 </​nowiki>​ </​nowiki>​
algorithm/dijkstras.1464070973.txt.gz · Last modified: 2016/05/23 23:22 by will