Dijkstra.js

/**
 * Created by VV on 2/3/2016.
 */
"use strict";

function PriorityQueue(){
    this._nodes = [];

    this.enqueue = function (priority, item){
        this._nodes.push({priority: priority, item: item});
        this.sort();
    }

    this.dequeue = function () {
        return this._nodes.shift().item;
    }

    this.sort = function(){
        this._nodes.sort(function(a, b){
           return a.priority - b.priority;
        });
    }

    this.isEmpty = function(){
        return !this._nodes.length;
    }

    this.count = function(){
        return this._nodes.length;
    }
}

function Graph(){
    this.vertices = {};

    this.addVertex = function(name, edges){
        this.vertices[name] = edges;
    }

    this.shortestPath = function(start, finish){
        var INFINITY = 1/0;
        var nodes = new PriorityQueue();
        var distances = {};
        var previous = {};
        var path = [];
        var smallest;


        for(var vertex in this.vertices){
            if (vertex === start){
                distances[vertex] = 0;
                nodes.enqueue(0, vertex);
            } else {
                distances[vertex] = INFINITY;
                nodes.enqueue(INFINITY, vertex);
            }

            previous[vertex] = null;
        }

        while(!nodes.isEmpty()){
            console.log('%s items in the queue', nodes.count());
            smallest = nodes.dequeue();
            console.log('Visiting %s', smallest);


            // if we found the finish then build the path by walking previous steps
            if(smallest === finish){
                console.log('Found finish %s', finish);
                console.log('Distance to finish: %s', distances[smallest]);

                // lets' check if finish is reacheable
                if(distances[finish] === INFINITY){
                    return [];
                }

                var u = finish;
                while (previous[u]) {
                    path.unshift(u);
                    u = previous[u];
                };
                path.unshift(start);


                break;
            }

            if(distances[smallest] === INFINITY) {
                continue;
            }

            // recalculate each vertex distance

            for(var neighbour in this.vertices[smallest]){
                console.log('Recalculating distance for %s. Current distance is %s', neighbour, distances[neighbour]);
                var newDistance = distances[smallest] + this.vertices[smallest][neighbour];

                if (newDistance < distances[neighbour]){
                    console.log('Updating the distance for %s. New distance is %s', neighbour, newDistance);
                    distances[neighbour] = newDistance;
                    previous[neighbour] = smallest;

                    nodes.enqueue(newDistance, neighbour);
                }
            }

        }


        return path;
    }
}

var graph = new Graph();
graph.addVertex("a1", {"b3":1, "c2":1});
//graph.addVertex("b3", {"c1":1, "a1":1});
graph.addVertex("b3", { "a1":1});
graph.addVertex("c1", {"b3":1});
graph.addVertex("c2", {"a1":1});

var start = 'a1', finish = 'c1';
var path = graph.shortestPath(start, finish);
console.log('The shortest path from %s to %s is: ', start, finish, path);


var g = new Graph();

g.addVertex('A', {B: 7, C: 8});
g.addVertex('B', {A: 7, F: 2});
g.addVertex('C', {A: 8, F: 6, G: 4});
g.addVertex('D', {F: 8});
g.addVertex('E', {H: 1});
g.addVertex('F', {B: 2, C: 6, D: 8, G: 9, H: 3});
g.addVertex('G', {C: 4, F: 9});
g.addVertex('H', {E: 1, F: 3});

// Log test, with the addition of reversing the path and prepending the first node so it's more readable
console.log(g.shortestPath('A', 'H'));