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 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

32033

increased by11.92%

Lines of code

574

increased by20.84%

Number of lines in readme file

227

increased by1.79%

Worsened metrics

Number of package files

6

decreased by-14.29%

No dependency changes