Skip to content

Instantly share code, notes, and snippets.

@coltrane
Created October 29, 2012 05:59
Show Gist options
  • Save coltrane/3971837 to your computer and use it in GitHub Desktop.
Save coltrane/3971837 to your computer and use it in GitHub Desktop.
An implementation of Dijkstra's path-finding algorithm in javascript.
function node(name) {
if (node.all[name]) { return node.all[name]; }
if (!(this instanceof node)) { return new node(name); }
node.all[name] = this;
this.name = name;
this.links = [];
this.toString = function() { return name; }
}
node.all = {};
function link(n1, n2, cost) {
if( !(n1 instanceof node)) { n1 = node(n1); }
if( !(n2 instanceof node)) { n2 = node(n2); }
if(!(this instanceof link)) { return new link(n1,n2,cost); }
for(var i=0; i<n1.links.length; ++i) {
var l = n1.links[i];
if (l.n1 === n2 || l.n2 === n2) { l.cost = cost; return l; }
}
n1.links.push(this);
n2.links.push(this);
this.n1 = n1;
this.n2 = n2;
this.cost = cost;
this.toString = function() { return n1 + ">" + n2 + " (" + cost + ")"; }
this.far = function(near) { return (near==n2)?n1:n2; }
}
function path(prev, node, cost) {
if(!(this instanceof path)) { return new path(prev,node,cost); }
this.node = node;
this.cost = cost;
this.elements = function() {
var a = prev? prev.elements() : [];
a.push(this.node);
return a;
}
this.toString = function() {
return (prev?prev + ' > ':"") + node + " (" + cost + ")";
}
}
function insert_sorted(list, key, item) {
for(var i=0; i<list.length; ++i) {
if (list[i][key] > item[key]) { list.splice(i, 0, item); return list; }
}
list.push(item);
return list;
}
function findPath(from, to) {
if( !(from instanceof node)) { from = node(from); }
if( !(to instanceof node)) { to = node(to); }
var visited = { },
stack = [ path(null, from, 0) ],
cur;
while (cur = stack.shift()) {
console.log(cur.toString());
if( cur.node === to ) { return cur; }
for(var i=0; i<cur.node.links.length; ++i) {
var link = cur.node.links[i],
other = link.far(cur.node);
if (visited[other]) { continue; }
insert_sorted(stack, 'cost', path(cur, other, link.cost+cur.cost));
}
visited[cur.node] = true;
}
}
// build the graph
//
link('O', 'A', 1);
link('A', 'B', 11);
link('B', 'D', 2);
link('O', 'C', 7);
link('C', 'D', 1);
// now search it for least-cost route
// from "O" to "D"
//
findPath('O', 'D').toString();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment