Djikstra's algorithm in node / javascript

So tonight I had to implement Djikstra's algorithm to do some very simple pathfinding in an experimental thing I'm working on, so seeing as nothing has happened in June I decided I'll post the code.

Perhaps someone finds it useful some day, perhaps someone wants to discuss it or improve it. The code is very rough as I needed it *now*. Probably some bugs in there as well. I'm gonna start to use it now so I'll update the code as I find them :) I started of all functional but very quickly reverted back to old habits as the impending deadline loomed :)

Anyway, so it was fun writing some proper algorithm code again after how many years of businessy stuff :)

Djikstra in JS:

	var _ = require("underscore"),
	assert = require("assert");
	describe("Djikstra", function () {
	var links = [
	{from:"1",to:"2",cost:7},
	{from:"2",to:"1",cost:7},
	{from:"2",to:"3",cost:15},
	{from:"3",to:"2",cost:15},
	{from:"3",to:"4",cost:6},
	{from:"4",to:"3",cost:6},
	{from:"4",to:"5",cost:9},
	{from:"5",to:"4",cost:9},
	{from:"5",to:"6",cost:2},
	{from:"6",to:"5",cost:2},
	{from:"6",to:"1",cost:9},
	{from:"1",to:"6",cost:9},
	{from:"2",to:"6",cost:10},
	{from:"6",to:"2",cost:10},
	{from:"3",to:"6",cost:11},
	{from:"6",to:"3",cost:11}
	],
	INFINITY = 99999;
	var entries = function (m) {
	return _(_(m).keys()).map(function (x) {
	return [x, m[x]];
	});
	};
	var djikstra = function (n, to, links) {
	var labels = _(links).chain().map(function (x) {
	return [x.from,x.to];
	}).flatten().uniq().value(),
	getLinks = function (x) {
	return _(links).filter(function (n) { return n.from === x; });
	},
	getUnvisitedLinks = function (n) {
	return _(getLinks(n)).filter(function (x) { return _(stillUnvisited).contains(x.to); });
	},
	initialNode = n,
	dist = _(labels).reduce(function (x, y) {
	x[y] = y === initialNode ? 0 : INFINITY;
	return x;
	}, {}),
	paths = {},
	stillUnvisited = labels.slice(), // this copies the list
	previous = [initialNode],
	updateTentativeCost = function (x,y) {
	x[y.to] = y.cost + dist[initialNode];
	return x;
	},
	updateIfSmaller = function (x) {
	if (x[1] < dist[x[0]]) {
	dist[x[0]] = x[1];
	paths[x[0]] = initialNode;
	}
	},
	filterUnvisited = function (x) {
	return stillUnvisited.indexOf(x[0]) !== -1;
	};
	while (stillUnvisited.length > 0) {
	// get the node with the shortest distance thus far
	initialNode = _(entries(dist)).chain().filter(filterUnvisited).sortBy("1").value()[0][0];
	if (initialNode === to) break; // we have finished searching
	if (dist[initialNode] === INFINITY) break; // we can't get to any more nodes from this one
	stillUnvisited = _(stillUnvisited).without(initialNode);
	var unvisitedLinks = getUnvisitedLinks(initialNode),
	tentative = _(unvisitedLinks).reduce(updateTentativeCost, {});
	_(entries(tentative)).each(updateIfSmaller);
	}
	var getPrevious = function (x) {
	return paths[x];
	};
	var path = [to],
	cur = to;
	while (getPrevious(cur)) {
	path.push(getPrevious(cur));
	cur = getPrevious(cur);
	}
	path = _(path).reverse();
	return path;
	};
	it("should work", function () {
	var p = djikstra("1", "4",links);
	assert.equal(true, _.isEqual(["1", "6", "5", "4"], p));
	});
	});

view raw djikstra.js hosted with ❤ by GitHub