Dijkstra

dijkstra_algorithm.js

//create data structure for dijkstra algo hotness
var Node = function(name) {
    this.name = name;
    this.neighbors = [];
};
Node.prototype = {

    neighbors : null,

    addNeighbor : function(node, distance) {
        this.neighbors.push({
            'distance' : distance,
            'node' : node
        });
        return this;
    },

    // process.nextTick(mindz.blown)
    dijkstrafy : function() {
        var visited = {};

        (function traverse(node, previousDistance) {
            // previousDistance = previousDistance||0;
            node.neighbors.forEach(function(neighbor) {
                var distance = neighbor.distance+(previousDistance||0);

                //recurse to edge (no neighbors)
                if(neighbor.node.neighbors) {
                    traverse(neighbor.node, (previousDistance||0)+neighbor.distance);
                }

                //compare neighbor's total distance to visited distance, store lowest
                if( distance < (visited[neighbor.node.name]||Infinity)) {
                    visited[neighbor.node.name] = distance;
                }
            });
        }(this));

        //mindz === blown
        return visited;
    }

};

var result,
    assert = require('assert'),
    v0 = new Node('v0'),
    v1 = new Node('v1'),
    v2 = new Node('v2'),
    v3 = new Node('v3'),
    v4 = new Node('v4'),
    v5 = new Node('v5');

v0
    .addNeighbor(v1, 2)
    .addNeighbor(v5, 9);

v1
    .addNeighbor(v5, 6)
    .addNeighbor(v2, 8)
    .addNeighbor(v3, 15);

v2
    .addNeighbor(v3, 1);

v4
    .addNeighbor(v3, 3)
    .addNeighbor(v2, 7);

v5
    .addNeighbor(v4, 3);

result = v0.dijkstrafy();
assert.deepEqual(
    { v1: 2, v2: 10, v3: 11, v4: 11, v5: 8 },
    result,
    'epic fail: '+JSON.stringify(result)
);
console.log('legendary ', result);