improve dfs/shortest_path

64json · 64json · commit f635cdc4bad1 · 2016-06-03T14:27:14.000+09:00
diff --git a/algorithm/graph_search/dfs/shortest_path/code.js b/algorithm/graph_search/dfs/shortest_path/code.js
@@ -2,10 +2,10 @@ function DFS(node, parent, weight) { // node = current node, parent = previous n
     if (minWeight < weight) return;
     if (node == e) {
         tracer._visit(node, parent, weight)._wait();
-        tracer._leave(node, parent, 0)._wait();
         if (minWeight > weight) {
             minWeight = weight;
         }
+        tracer._leave(node, parent, minWeight)._wait();
         return;
     }
     D[node] = true; // label current node as discovered
diff --git a/algorithm/graph_search/dfs/shortest_path/data.js b/algorithm/graph_search/dfs/shortest_path/data.js
@@ -1,5 +1,5 @@
 var tracer = new WeightedDirectedGraphTracer();
 var logger = new LogTracer();
 tracer.attach(logger);
-var G = WeightedDirectedGraph.random(10, .3, 1, 9);
+var G = WeightedDirectedGraph.random(5, 1, 1, 9);
 tracer._setData(G);

Original file line number	Diff line number	Diff line change
`@@ -2,10 +2,10 @@ function DFS(node, parent, weight) { // node = current node, parent = previous n`
`2`	`2`	`if (minWeight < weight) return;`
`3`	`3`	`if (node == e) {`
`4`	`4`	`tracer._visit(node, parent, weight)._wait();`
`5`		`- tracer._leave(node, parent, 0)._wait();`
`6`	`5`	`if (minWeight > weight) {`
`7`	`6`	`minWeight = weight;`
`8`	`7`	`}`
	`8`	`+ tracer._leave(node, parent, minWeight)._wait();`
`9`	`9`	`return;`
`10`	`10`	`}`
`11`	`11`	`D[node] = true; // label current node as discovered`