Dijkstra's Algorithm in JavaScript

I happend to read through a series of blog posts by Nicholas C. Zakas here - http://www.nczonline.net/blog/2009/06/09/computer-science-in-javascript-binary-search-tree-part-1. These are really interesting thoughts. So I decided to take it another step by implementing the shortest span/path solution using Dijkstra's Algorithm. A beautiful explanation of the algorithm is available in YouTube at - http://www.youtube.com/watch?v=8Ls1RqHCOPw - so that I can stay focussed on the implementation part.

Now, let me walk you through the steps taken to implement the algorithm in javascript.

First of all, I need to define the graph that I am going to traverse. The best way to represent the graph is in metrix form, where each of the entry will indicate the weighted edge from one node to the other. To do this in JS, I created an array of arrays, with a header element at the first row.

Figure 1.

The above graph can be represented as follows.    

[['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'],

/* A */  [ 0 ,  20,  0 ,  80,  0 ,  0 ,  90,  0 ],

/* B */  [ 0 ,  0 ,  0 ,  0 ,  0 ,  10,  0 ,  0 ],

/* C */  [ 0 ,  0 ,  0 ,  10,  0 ,  50,  0 ,  20],

/* D */  [ 0 ,  0 ,  10,  0 ,  0 ,  0 ,  20,  0 ],

/* E */  [ 0 ,  50,  0 ,  0 ,  0 ,  0 ,  30,  0 ],

/* F */  [ 0 ,  0 ,  10,  40,  0 ,  0 ,  0 ,  0 ],

/* G */  [ 20,  0 ,  0 ,  0 ,  0 ,  0 ,  0 ,  0 ],

/* H */  [ 0 ,  0 ,  0 ,  0 ,  0 ,  0 ,  0 ,  0 ]];

Please note that, this is just to load the information in the graph data structure.

Now lets see how we can define graph. Basically, a graph - similar to the one in figure 1 - will have multiple nodes only. So definig graph is simple as follows.

function Graph() { 
  this._nodes = [];
  // Just to access the number of nodes easily without checking the array length.
  this._count = 0;

}

Now think about the graph nodes. Starting from first node, every node will have a name or and indentifier, and a number of adjacent nodes. For each of the adjacent nodes, there will be a distance/costs/weights to reach to the nodes. That gives us two properties adjacentNodes array and weights array. So we can define the constructor as follows:

function GraphNode(nm) {
  this._adjacentNodes = [];
  this._weights = [];
  this.name = nm;
}

Now we just need to define some APIs in Graph prototype for loading initial data, traversing through the nodes to find the shortest path etc. Below are the methods added to the graph.

Graph.prototype = {
  constructor: Graph, 

  // Add a node to the collection

  addNode : function(node){

  .

  .
  },

  // Add a weighted edge to the node 'from' to the node 'to'
  addDirectedEdge : function (from, to, weight){

  },

  // Initialize the node with graph matrics array. 
  createNodes: function(adjWM) {
    .

    .

  }

}

Before I show the full code and demo, let me outline the steps to find out the shortest path as per this implementation.

1. Initialize shortest path to reach to any node as infinity (or Number.MAX_VALUE). This adds one more property to the GraphNode.
2. Start from any node, set the shortest path to reach to this node as zero. Call this as current node.
3. Loop throgh all adjacent nodes, and set the shortest path to reach to those nodes as the sum of shortest path to reach the current node and the weight of the adjacent node. If you find any new lower shortest path to any node, discard the previous and set the new shortest path.
4. Move to the node with lowest shortest path at this time. Set this as current node and repeat the step 3 & 4. 

Here is a demo you can view or download.  

Below is the output after running with jsunit testing (closure library).