bellman_ford: update weight of each node

64json · 64json · commit 22fcb4ab4c14 · 2016-05-22T22:33:01.000-05:00
diff --git a/algorithm/graph_search/bellman_ford/shortest_path/code.js b/algorithm/graph_search/bellman_ford/shortest_path/code.js
@@ -3,8 +3,10 @@ function BELLMAN_FORD (src, dest) {
 
 	for (var i = 0; i < G.length; i++) {
 		weights [i] = MAX_VALUE;
+        tracer._weight(i, weights[i]);
 	}
 	weights [src] = 0;
+    tracer._weight(src, 0);
 
 	tracer._print ('Initializing weights to: [' +  weights + ']');
 	tracer._print ('');
@@ -19,14 +21,13 @@ function BELLMAN_FORD (src, dest) {
 			for (var currentNodeNeighbor = 0; currentNodeNeighbor <= G.length; currentNodeNeighbor++) {
 				if (G [currentNode] [currentNodeNeighbor]) {	//proceed to relax Edges only if a particular weight != 0 (0 represents no edge)
 					tracer._print ('Exploring edge from ' + currentNode + ' to ' + currentNodeNeighbor + ', weight = ' + G [currentNode] [currentNodeNeighbor]);
-					tracer._visit (currentNodeNeighbor, currentNode, undefined);
 
 					if ( weights [currentNodeNeighbor] > (weights [currentNode] + G [currentNode] [currentNodeNeighbor]) ) {
 						weights [currentNodeNeighbor] = weights [currentNode] + G [currentNode] [currentNodeNeighbor];
 						tracer._print ('weights [' + currentNodeNeighbor + '] = weights [' + currentNode + '] + ' + G [currentNode] [currentNodeNeighbor]);
 					}
-
-					tracer._leave (currentNodeNeighbor, currentNode, undefined);
+                    tracer._visit (currentNodeNeighbor, currentNode, weights [currentNodeNeighbor]);
+					tracer._leave (currentNodeNeighbor, currentNode);
 				}
 			}
 		}

Original file line number	Diff line number	Diff line change
`@@ -3,8 +3,10 @@ function BELLMAN_FORD (src, dest) {`
`3`	`3`
`4`	`4`	`for (var i = 0; i < G.length; i++) {`
`5`	`5`	`weights [i] = MAX_VALUE;`
	`6`	`+ tracer._weight(i, weights[i]);`
`6`	`7`	`}`
`7`	`8`	`weights [src] = 0;`
	`9`	`+ tracer._weight(src, 0);`
`8`	`10`
`9`	`11`	`tracer._print ('Initializing weights to: [' + weights + ']');`
`10`	`12`	`tracer._print ('');`
`@@ -19,14 +21,13 @@ function BELLMAN_FORD (src, dest) {`
`19`	`21`	`for (var currentNodeNeighbor = 0; currentNodeNeighbor <= G.length; currentNodeNeighbor++) {`
`20`	`22`	`if (G [currentNode] [currentNodeNeighbor]) { //proceed to relax Edges only if a particular weight != 0 (0 represents no edge)`
`21`	`23`	`tracer._print ('Exploring edge from ' + currentNode + ' to ' + currentNodeNeighbor + ', weight = ' + G [currentNode] [currentNodeNeighbor]);`
`22`		`- tracer._visit (currentNodeNeighbor, currentNode, undefined);`
`23`	`24`
`24`	`25`	`if ( weights [currentNodeNeighbor] > (weights [currentNode] + G [currentNode] [currentNodeNeighbor]) ) {`
`25`	`26`	`weights [currentNodeNeighbor] = weights [currentNode] + G [currentNode] [currentNodeNeighbor];`
`26`	`27`	`tracer._print ('weights [' + currentNodeNeighbor + '] = weights [' + currentNode + '] + ' + G [currentNode] [currentNodeNeighbor]);`
`27`	`28`	`}`
`28`		`-`
`29`		`- tracer._leave (currentNodeNeighbor, currentNode, undefined);`
	`29`	`+ tracer._visit (currentNodeNeighbor, currentNode, weights [currentNodeNeighbor]);`
	`30`	`+ tracer._leave (currentNodeNeighbor, currentNode);`
`30`	`31`	`}`
`31`	`32`	`}`
`32`	`33`	`}`