Djikstra's algorithm for node

djikstra.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));
    });
});