skeep · August 13, 2018 19:43 · Sep 21, 2016 · Sep 21, 2016 · Sep 21, 2016 · Sep 21, 2016
diff --git a/Dijkstra.js b/Dijkstra.js
@@ -1,4 +1,7 @@
-// Basic Graph data structure implementation
+/**
+ * Basic Graph data structure implementation
+ * @constructor
+ */
 var Graph = function() {
     this.vertices = {};
 };

diff --git a/Dijkstra.js b/Dijkstra.js
@@ -16,7 +16,6 @@ Graph.prototype.length = function(u, v) {
  * Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph
  * @param source
  * @returns {{}}
- * @constructor
  */
 Graph.prototype.Dijkstra = function(source) {
     // create vertex set Q

diff --git a/Dijkstra.js b/Dijkstra.js
@@ -12,7 +12,12 @@ Graph.prototype.length = function(u, v) {
     return (this.vertices[u][v]);
 };
 
-// function Dijkstra(Graph, source):
+/**
+ * Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph
+ * @param source
+ * @returns {{}}
+ * @constructor
+ */
 Graph.prototype.Dijkstra = function(source) {
     // create vertex set Q
     var Q = {},

diff --git a/Dijkstra.js b/Dijkstra.js
@@ -20,10 +20,10 @@ Graph.prototype.Dijkstra = function(source) {
         prev = {};
 
     /**
-     * 5      for each vertex v in Graph:             // Initialization
-     * 6          dist[v] ← INFINITY                  // Unknown distance from source to v
-     * 7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
-     * 8          add v to Q                          // All nodes initially in Q (unvisited nodes)
+     * for each vertex v in Graph:             // Initialization
+     *     dist[v] ← INFINITY                  // Unknown distance from source to v
+     *     prev[v] ← UNDEFINED                 // Previous node in optimal path from source
+     *     add v to Q                          // All nodes initially in Q (unvisited nodes)
      */
     for (var vertex in this.vertices) {
         dist[vertex] = Infinity;
@@ -50,8 +50,8 @@ Graph.prototype.Dijkstra = function(source) {
 
             /**
              * if alt < dist[v]:               // A shorter path to v has been found
-             *   dist[v] ← alt
-             *   prev[v] ← u
+             *     dist[v] ← alt
+             *     prev[v] ← u
              */
             if (alt < dist[neighbor]) {
                 dist[neighbor] = alt;

diff --git a/Dijkstra.js b/Dijkstra.js
@@ -1,25 +1,3 @@
-function _isEmpty(obj) {
-    return Object.keys(obj).length === 0;
-}
-
-/**
- * Extract the node with minimum distance from active vertex.
- * This should not be required if using a priority queue
- */
-
-function _extractMin(Q, dist) {
-    var minimumDistance = Infinity;
-    var nodeWithMinimumDistance;
-
-    for (var node in Q) {
-        if (dist[node] <= minimumDistance) {
-            minimumDistance = dist[node];
-            nodeWithMinimumDistance = node;
-        }
-    }
-    return nodeWithMinimumDistance;
-}
-
 // Basic Graph data structure implementation
 var Graph = function() {
     this.vertices = {};
@@ -92,3 +70,34 @@ G.add('V', { W: 2, T: 6 });
 G.add('T');
 
 console.log(G.Dijkstra('S'));
+
+/**
+ * Just a utility method to check if an Object is empty or not
+ * @param obj
+ * @returns {boolean}
+ * @private
+ */
+function _isEmpty(obj) {
+    return Object.keys(obj).length === 0;
+}
+
+/**
+ * Extract the node with minimum distance from active vertex.
+ * This should not be required if using a priority queue
+ * @param Q
+ * @param dist
+ * @returns {*}
+ * @private
+ */
+function _extractMin(Q, dist) {
+    var minimumDistance = Infinity;
+    var nodeWithMinimumDistance;
+
+    for (var node in Q) {
+        if (dist[node] <= minimumDistance) {
+            minimumDistance = dist[node];
+            nodeWithMinimumDistance = node;
+        }
+    }
+    return nodeWithMinimumDistance;
+}
diff --git a/Dijkstra.js b/Dijkstra.js
@@ -2,6 +2,11 @@ function _isEmpty(obj) {
     return Object.keys(obj).length === 0;
 }
 
+/**
+ * Extract the node with minimum distance from active vertex.
+ * This should not be required if using a priority queue
+ */
+
 function _extractMin(Q, dist) {
     var minimumDistance = Infinity;
     var nodeWithMinimumDistance;
@@ -15,6 +20,7 @@ function _extractMin(Q, dist) {
     return nodeWithMinimumDistance;
 }
 
+// Basic Graph data structure implementation
 var Graph = function() {
     this.vertices = {};
 };

diff --git a/Dijkstra.js b/Dijkstra.js
@@ -28,6 +28,7 @@ Graph.prototype.length = function(u, v) {
     return (this.vertices[u][v]);
 };
 
+// function Dijkstra(Graph, source):
 Graph.prototype.Dijkstra = function(source) {
     // create vertex set Q
     var Q = {},

diff --git a/Dijkstra.js b/Dijkstra.js
@@ -34,26 +34,45 @@ Graph.prototype.Dijkstra = function(source) {
         dist = {},
         prev = {};
 
+    /**
+     * 5      for each vertex v in Graph:             // Initialization
+     * 6          dist[v] ← INFINITY                  // Unknown distance from source to v
+     * 7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
+     * 8          add v to Q                          // All nodes initially in Q (unvisited nodes)
+     */
     for (var vertex in this.vertices) {
         dist[vertex] = Infinity;
         prev[vertex] = undefined;
         Q[vertex] = this.vertices[vertex];
     }
 
+    // dist[source] ← 0  // Distance from source to source
+
     dist[source] = 0;
 
+    // while Q is not empty:
     while (!_isEmpty(Q)) {
+        // u ← vertex in Q with min dist[u]    // Source node will be selected first
         var u = _extractMin(Q, dist);
+
+        // remove u from Q
         delete Q[u];
 
+        // for each neighbor v of u:           // where v is still in Q.
         for (var neighbor in this.vertices[u]) {
+            // alt ← dist[u] + length(u, v)
             var alt = dist[u] + G.length(u, neighbor);
+
+            /**
+             * if alt < dist[v]:               // A shorter path to v has been found
+             *   dist[v] ← alt
+             *   prev[v] ← u
+             */
             if (alt < dist[neighbor]) {
                 dist[neighbor] = alt;
                 prev[neighbor] = u;
             }
         }
-
     }
     return dist;
 };

diff --git a/Dijkstra.js b/Dijkstra.js
@@ -0,0 +1,68 @@
+function _isEmpty(obj) {
+    return Object.keys(obj).length === 0;
+}
+
+function _extractMin(Q, dist) {
+    var minimumDistance = Infinity;
+    var nodeWithMinimumDistance;
+
+    for (var node in Q) {
+        if (dist[node] <= minimumDistance) {
+            minimumDistance = dist[node];
+            nodeWithMinimumDistance = node;
+        }
+    }
+    return nodeWithMinimumDistance;
+}
+
+var Graph = function() {
+    this.vertices = {};
+};
+
+Graph.prototype.add = function(name, edges) {
+    edges = edges || null;
+    this.vertices[name] = edges;
+};
+
+Graph.prototype.length = function(u, v) {
+    return (this.vertices[u][v]);
+};
+
+Graph.prototype.Dijkstra = function(source) {
+    // create vertex set Q
+    var Q = {},
+        dist = {},
+        prev = {};
+
+    for (var vertex in this.vertices) {
+        dist[vertex] = Infinity;
+        prev[vertex] = undefined;
+        Q[vertex] = this.vertices[vertex];
+    }
+
+    dist[source] = 0;
+
+    while (!_isEmpty(Q)) {
+        var u = _extractMin(Q, dist);
+        delete Q[u];
+
+        for (var neighbor in this.vertices[u]) {
+            var alt = dist[u] + G.length(u, neighbor);
+            if (alt < dist[neighbor]) {
+                dist[neighbor] = alt;
+                prev[neighbor] = u;
+            }
+        }
+
+    }
+    return dist;
+};
+
+// Usage
+var G = new Graph();
+G.add('S', { V: 1, W: 4 });
+G.add('W', { T: 3 });
+G.add('V', { W: 2, T: 6 });
+G.add('T');
+
+console.log(G.Dijkstra('S'));