graph-data-structure - npm Package Compare versions

Comparing version 1.0.0 to 1.1.0

index.js

@@ -18,2 +18,3 @@ // A graph data structure with depth-first search and topological sort.
     topologicalSort: topologicalSort,
+    shortestPath: shortestPath,
     serialize: serialize,
@@ -198,2 +199,87 @@ deserialize: deserialize
 
+  // Dijkstra's Shortest Path Algorithm.
+  // Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 658
+  // Variable and function names correspond to names in the book.
+  function shortestPath(source, destination){
+
+    // Upper bounds for shortest path weights from source.
+    var d = {};
+
+    // Predecessors.
+    var p = {};
+
+    // Poor man's priority queue, keyed on d.
+    var q = {};
+
+    function initializeSingleSource(){
+      nodes().forEach(function (node){
+        d[node] = Infinity;
+      });
+      d[source] = 0;
+    }
+
+    // Adds entries in q for all nodes.
+    function initializePriorityQueue(){
+      nodes().forEach(function (node){
+        q[node] = true;
+      });
+    }
+
+    // Returns true if q is empty.
+    function priorityQueueEmpty(){
+      return Object.keys(q).length === 0;
+    }
+
+    // Linear search to extract (find and remove) min from q.
+    function extractMin(){
+      var min = Infinity;
+      var minNode;
+      Object.keys(q).forEach(function(node){
+        if (d[node] < min) {
+          min = d[node];
+          minNode = node;
+        }
+      });
+      delete q[minNode];
+      return minNode;
+    }
+
+    function relax(u, v){
+      var w = getEdgeWeight(u, v);
+      if (d[v] > d[u] + w) {
+        d[v] = d[u] + w;
+        p[v] = u;
+      }
+    }
+
+    function dijkstra(){
+      initializeSingleSource();
+      initializePriorityQueue();
+      while(!priorityQueueEmpty()){
+        var u = extractMin();
+        adjacent(u).forEach(function (v){
+          relax(u, v);
+        });
+      }
+    }
+
+    // Assembles the shortest path by traversing the
+    // predecessor subgraph from destination to source.
+    function path(){
+      var nodeList = [];
+      var node = destination;
+      while(p[node]){
+        nodeList.push(node);
+        node = p[node];
+      }
+      nodeList.push(source);
+      nodeList.reverse();
+      return nodeList;
+    }
+
+    dijkstra();
+
+    return path();
+  }
+
   // Serializes the graph.
@@ -200,0 +286,0 @@ function serialize(){

package.json

 {
   "name": "graph-data-structure",
-  "version": "1.0.0",
+  "version": "1.1.0",
   "description": "A graph data structure with topological sort.",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

@@ -223,1 +223,5 @@ # graph-data-structure
 </p>
+
+<a name="shortest-path" href="#shortest-path">#</a> <i>graph</i>.<b>shortestPath</b>(<i>sourceNode</i>, <i>destinationNode</i>)
+
+Performs [Dijkstras Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). Returns an array of node identifier strings. The returned array includes the nodes of the shortest path from source to destination node. Inspired by by Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 658.

test.js

@@ -335,2 +335,33 @@
   });
+
+  describe("Dijkstra's Shortest Path Algorithm", function (){
+
+    it("Should compute shortest path on a single edge.", function (){
+      var graph = Graph().addEdge("a", "b");
+      assert.deepEqual(graph.shortestPath("a", "b"), ["a", "b"]);
+    });
+
+    it("Should compute shortest path on two edges.", function (){
+      var graph = Graph()
+        .addEdge("a", "b")
+        .addEdge("b", "c");
+      assert.deepEqual(graph.shortestPath("a", "c"), ["a", "b", "c"]);
+    });
+
+    it("Should compute shortest path on example from Cormen text (p. 659).", function (){
+      var graph = Graph()
+        .addEdge("s", "t", 10)
+        .addEdge("s", "y", 5)
+        .addEdge("t", "y", 2)
+        .addEdge("y", "t", 3)
+        .addEdge("t", "x", 1)
+        .addEdge("y", "x", 9)
+        .addEdge("y", "z", 2)
+        .addEdge("x", "z", 4)
+        .addEdge("z", "x", 6);
+      assert.deepEqual(graph.shortestPath("s", "z"), ["s", "y", "z"]);
+      assert.deepEqual(graph.shortestPath("s", "x"), ["s", "y", "t", "x"]);
+    });
+
+  });
 });
@@ -337,0 +368,0 @@

No alert changes

Improved metrics

Total package byte prevSize

32033

11.92%

Lines of code

574

20.84%

Number of lines in readme file

227

1.79%

Worsened metrics

Number of package files

6

-14.29%

No dependency changes