Advertisement
Guest User

Javascript Dijkstra's Algorithm

a guest
Oct 28th, 2012
546
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. function pathFinder(startNode,endNode,sourceGraph) {
  2.     var copyGraph = sourceGraph;
  3.     var sNode = copyGraph.nodes[copyGraph.nodes.indexOf(startNode)];
  4.     var eNode = copyGraph.nodes[copyGraph.nodes.indexOf(endNode)];
  5.     var ALGORITHM = true;
  6.     var TDISTANCE = 0;
  7.     for (var n in copyGraph) {
  8.         if (n instanceof Node) {
  9.             n.distance = Infinity;
  10.             n.visited = false;
  11.         }
  12.     }
  13.     sNode.distance = 0;
  14.     var unvisited = copyGraph.nodes;
  15.     unvisited.splice(unvisited.indexOf(sNode),1);
  16.     var path = [];
  17.     var previous = [];
  18.     var currentNode = sNode;
  19.     while (ALGORITHM) {
  20.         var connectedNodes = [];
  21.         for (var i=0;i<currentNode.edges.length;i++) {
  22.             var length = currentNode.edges[i].v;
  23.             if (currentNode.edges[i].c1 != currentNode && !currentNode.edges[i].c1.visited) {
  24.                 if (currentNode.distance+length < currentNode.edges[i].c1.distance) {
  25.                     currentNode.edges[i].c1.distance = currentNode.distance+length;
  26.                 }
  27.                 connectedNodes.push(currentNode.edges[i].c1);
  28.             } else if (currentNode.edges[i].c2 != currentNode && !currentNode.edges[i].c2.visited) {
  29.                 if (currentNode.distance+length < currentNode.edges[i].c2.distance) {
  30.                     currentNode.edges[i].c2.distance = currentNode.distance+length;
  31.                 }
  32.                 connectedNodes.push(currentNode.edges[i].c2);
  33.             }
  34.         }
  35.         var bestConnected = connectedNodes.sort(function(a,b) { return a.distance-b.distance; })[0];
  36.         unvisited.splice(unvisited.indexOf(currentNode),1);
  37.         currentNode.visited = true;
  38.         currentNode = best;
  39.         path.push(currentNode);
  40.         if (currentNode == eNode) {
  41.             ALGORITHM = false;
  42.             break; 
  43.         }
  44.     }
  45.     return path;
  46. }
  47. //
  48. var Node = function(name) { this.n = name; this.distance = 0, this.visited = false, this.edges = []; };
  49. Node.prototype.setAsEdge = function(edge) { this.edges.push(edge); };
  50. var gNode = function(node,x,y,radius) { this.node = node, this.x = x, this.y = y, this.radius = radius; };
  51. var Edge = function(connect1, connect2, value) { this.c1 = connect1; this.c2 = connect2; this.v = value; connect1.setAsEdge(this); connect2.setAsEdge(this); };
  52. var gEdge = function(edge,x1,y1,x2,y2,midpoint) { this.edge = edge, this.endPoints = [[x1,y1],[x2,y2]], this.m = midpoint};
  53. var Graph = function(nodes,edges) { this.nodes = nodes; this.edges = edges; };
  54. var gGraph = function(graph, canvas, canvasContext) { this.graph = graph; this.canvas = canvas; this.ctxt = canvasContext; this.graphicalNodes = [], this.graphicalEdges = []; };
  55. gGraph.prototype.draw = function(c) {
  56.     var NODE_RADIUS = 7;
  57.     for (var i=0;i<this.graph.nodes.length;i++) {
  58.         var x = Math.floor((Math.random()*(this.canvas.width-14))+14);
  59.         var y = Math.floor((Math.random()*(this.canvas.height-14))+14);
  60.         c.beginPath();
  61.         c.arc(x,y,NODE_RADIUS,0,2*Math.PI);
  62.         c.stroke();
  63.         c.fillText(String(this.graph.nodes[i].n),x-3,y+3);
  64.         this.graphicalNodes.push(new gNode(this.graph.nodes[i],x,y,NODE_RADIUS));
  65.     }
  66.     for (var i=0;i<this.graph.edges.length;i++) {
  67.         var x1 = this.graphicalNodes[this.graph.nodes.indexOf(this.graph.edges[i].c1)].x + NODE_RADIUS;
  68.         var y1 = this.graphicalNodes[this.graph.nodes.indexOf(this.graph.edges[i].c1)].y + NODE_RADIUS/2;
  69.         var x2 = this.graphicalNodes[this.graph.nodes.indexOf(this.graph.edges[i].c2)].x + NODE_RADIUS;
  70.         var y2 = this.graphicalNodes[this.graph.nodes.indexOf(this.graph.edges[i].c2)].y + NODE_RADIUS/2;
  71.         var m = [(x1+x2)/2,(y1+y2)/2];
  72.         c.beginPath();
  73.         c.moveTo(x1,y1);
  74.         c.lineTo(x2,y2);
  75.         c.stroke();
  76.         c.fillText(String(this.graph.edges[i].v),m[0],m[1]);
  77.         this.graphicalEdges.push(new gEdge(this.graph.edges[i],x1,y1,x2,y2,m));
  78.     }
  79. }
  80. //
  81. var simpleGraph = new Graph([],[]);
  82. var simpleGraphicalGraph;
  83. function runMe() {
  84.     for (var i=0;i<6;i++) {
  85.         simpleGraph.nodes.push(new Node(i+1)); 
  86.     }
  87.     simpleGraph.edges.push(new Edge(simpleGraph.nodes[0],simpleGraph.nodes[5],14));
  88.     simpleGraph.edges.push(new Edge(simpleGraph.nodes[0],simpleGraph.nodes[2],9));
  89.     simpleGraph.edges.push(new Edge(simpleGraph.nodes[0],simpleGraph.nodes[1],7));
  90.     simpleGraph.edges.push(new Edge(simpleGraph.nodes[1],simpleGraph.nodes[2],10));
  91.     simpleGraph.edges.push(new Edge(simpleGraph.nodes[1],simpleGraph.nodes[3],15));
  92.     simpleGraph.edges.push(new Edge(simpleGraph.nodes[2],simpleGraph.nodes[5],2));
  93.     simpleGraph.edges.push(new Edge(simpleGraph.nodes[2],simpleGraph.nodes[3],11));
  94.     simpleGraph.edges.push(new Edge(simpleGraph.nodes[3],simpleGraph.nodes[4],6));
  95.     simpleGraph.edges.push(new Edge(simpleGraph.nodes[5],simpleGraph.nodes[4],9));
  96.     simpleGraphicalGraph = graphToGraphicalGraph(simpleGraph,document.getElementById('theCanvas'));
  97.     simpleGraphicalGraph.draw(simpleGraphicalGraph.ctxt);
  98. }
  99. function graphToGraphicalGraph(graph,canvasElement) {
  100.     return new gGraph(graph,canvasElement,canvasElement.getContext('2d')); 
  101. }
  102. //
  103. window.addEventListener('load',runMe,false);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement