Djikstra's Algorithm

djikstra.js

function Djikstra(graph, source) {
    this.infinity = 1.7976931348623157E+10308;
    this.dist = {};
    this.previous = {};
    this.queue = [];
    
    // Get the smallest distance in the queue
    this.findSmallest = function() {
        var min = infinity;
        var smallest = null;
        for(var i=0;i<this.queue.length;i++) {
            if(this.dist[this.queue[i]] < min) {
                min = this.dist[this.queue[i]];
                smallest = this.queue[i];
            }
        }
        return smallest;
    };
    
    // Get the distances to all other nodes
    this.getDistances = function() {
        return this.dist;
    };
    
    // Get shortest path array from source to target
    this.getShortestPath = function(target) {
        var path = [];
        var temp = target;
        while(temp != undefined) {
            path.splice(0,0,temp);
            temp = this.previous[temp];
        }
        return path;
    };
    
    // Run the algorithm upon instantiation
    for(var node in graph.nodes) {
        this.dist[node] = infinity;
        this.previous[node] = null;
        this.queue.push(node);
    }
    this.dist[source] = 0;
    
    while(this.queue.length > 0) {
        var smallest = this.findSmallest();
        if(smallest == null || this.dist[smallest] == infinity) break;
        var index = 0;
        // Find the index in the queue that has the smallest id
        for(var i=0;i<this.queue.length;i++) {
            if(this.queue[i] == smallest) {
                index = i;
                break;
            }
        }
        this.queue.splice(index, 1);
        var neighbors = graph.neighbors(smallest);
        for(var i=0;i<neighbors.length;i++) {
            var distance = this.dist[smallest] + graph.getEdgeValue(smallest, neighbors[i]);
            // Overwrite current distance with this aggregate (will visit all nodes up to this and tally the distances)
            if(distance < this.dist[neighbors[i]]) {
                this.dist[neighbors[i]] = distance;
                this.previous[neighbors[i]] = smallest;
            }
        }
    }
    return this;
}
var djikstra = Djikstra(graph, 'test');
console.log(djikstra.getDistances());
console.log(djikstra.getShortestPath('test3'));