improve dijkstra

64json · 64json · commit 1b928eb4c5d5 · 2016-06-03T15:04:20.000+09:00
diff --git a/algorithm/graph_search/dijkstra/shortest_path/code.js b/algorithm/graph_search/dijkstra/shortest_path/code.js
@@ -3,7 +3,8 @@ function Dijkstra(start, end) {
     var D = []; // D[i] indicates whether the i-th node is discovered or not
     for (var i = 0; i < G.length; i++) D.push(false);
     S[start] = 0; // Starting node is at distance 0 from itself
-    tracerS._notify(start, S[start]);
+    tracerS._notify(start, S[start])._wait()._denotify(start);
+    tracerS._select(start);
     var k = G.length;
     while (k--) {
         // Finding a node with the shortest distance from S[minIndex]
@@ -16,15 +17,17 @@ function Dijkstra(start, end) {
         }
         if (minDistance == MAX_VALUE) break; // If there is no edge from current node, jump out of loop
         D[minIndex] = true;
-        tracerS._notify(minIndex);
+        tracerS._select(minIndex);
         tracer._visit(minIndex)._wait();
         // For every unvisited neighbour of current node, we check
         // whether the path to it is shorter if going over the current node
         for (i = 0; i < G.length; i++) {
             if (G[minIndex][i] && S[i] > S[minIndex] + G[minIndex][i]) {
                 S[i] = S[minIndex] + G[minIndex][i];
-                tracerS._notify(i, S[i])._wait()._denotify(i);
-                tracer._visit(i, minIndex, S[i])._wait()._leave(i, minIndex);
+                tracerS._notify(i, S[i]);
+                tracer._visit(i, minIndex, S[i])._wait();
+                tracerS._denotify(i);
+                tracer._leave(i, minIndex)._wait();
             }
         }
         tracer._leave(minIndex)._wait();
diff --git a/algorithm/graph_search/dijkstra/shortest_path/data.js b/algorithm/graph_search/dijkstra/shortest_path/data.js
@@ -1,8 +1,8 @@
-var tracer = new WeightedDirectedGraphTracer();
+var tracer = new WeightedUndirectedGraphTracer();
 var tracerS = new Array1DTracer();
 var logger = new LogTracer();
 tracer.attach(logger);
-var G = WeightedDirectedGraph.random(10, .4, 1, 9);
+var G = WeightedUndirectedGraph.random(5, 1, 1, 9);
 tracer._setData(G);
 var MAX_VALUE = Infinity;
 var S = []; // S[end] returns the distance from start node to end node
