Update bellman ford, edge and spec

mgechev · mgechev · commit 7ca316264c54 · 2015-05-07T17:56:08.000-07:00
diff --git a/src/data-structures/edge.js b/src/data-structures/edge.js
@@ -12,8 +12,8 @@
    * @module data-structures/edge
    */
   exports.Edge = function (e, v, distance) {
-    this.e = e;
-    this.v = v;
+    this.from = e;
+    this.to = v;
     this.distance = distance;
   };
 
diff --git a/src/graphs/shortest-path/bellman-ford.js b/src/graphs/shortest-path/bellman-ford.js
@@ -60,25 +60,27 @@
     var distances = {};
     var parents = {};
     var c;
-    for (var i = 0; i < vertexes.length; i += 1) {
-      distances[vertexes[i].id] = Infinity;
-      parents[vertexes[i].id] = null;
-    }
-    distances[source] = 0;
-    for (i = 0; i < vertexes.length - 1; i += 1) {
-      for (var j = 0; j < edges.length; j += 1) {
-        c = edges[j];
-        if (distances[c.from.id] + c.distance < distances[c.to.id]) {
-          distances[c.to.id] = distances[c.from.id] + c.distance;
-          parents[c.to.id] = c.from.id;
+    if (source) {
+      for (var i = 0; i < vertexes.length; i += 1) {
+        distances[vertexes[i].id] = Infinity;
+        parents[vertexes[i].id] = null;
+      }
+      distances[source.id] = 0;
+      for (i = 0; i < vertexes.length - 1; i += 1) {
+        for (var j = 0; j < edges.length; j += 1) {
+          c = edges[j];
+          if (distances[c.from.id] + c.distance < distances[c.to.id]) {
+            distances[c.to.id] = distances[c.from.id] + c.distance;
+            parents[c.to.id] = c.from.id;
+          }
         }
       }
-    }
 
-    for (i = 0; i < edges.length; i += 1) {
-      c = edges[i];
-      if (distances[c.from.id] + c.distance < distances[c.to.id]) {
-        return undefined;
+      for (i = 0; i < edges.length; i += 1) {
+        c = edges[i];
+        if (distances[c.from.id] + c.distance < distances[c.to.id]) {
+          return undefined;
+        }
       }
     }
 
diff --git a/test/graphs/shortest-path/bellman-ford.spec.js b/test/graphs/shortest-path/bellman-ford.spec.js
@@ -14,20 +14,23 @@ describe('Bellman-Ford', function () {
     var vs = [];
     var e = [];
     expect(bellmanFord(vs, e, undefined))
-      .toEqual({ parents: {}, distances: { undefined: 0 } });
+      .toEqual({ parents: {}, distances: {} });
   });
 
   it('should work for a graph with a single vertex', function () {
     var vs = [new Vertex(1)];
     var e = [];
-    expect(bellmanFord(vs, e, 1))
+    expect(bellmanFord(vs, e, vs[0]))
       .toEqual({ parents: { '1': null }, distances: { '1': 0 }});
   });
 
   it('should work in the general case', function () {
     var vs = [new Vertex(1), new Vertex(2), new Vertex(3)];
-    var e = [];
-    expect(bellmanFord(vs, e, 1))
-      .toEqual({ parents: { '1': null }, distances: { '1': 0 }});
+    var e = [new Edge(vs[0], vs[1], 2),
+      new Edge(vs[0], vs[2], 10),
+      new Edge(vs[1], vs[2], 1)
+    ];
+    var output = bellmanFord(vs, e, vs[0]);
+    expect(output.distances['3']).toBe(3);
   });
 });
