Improve dijkstra visualization

TornjV · TornjV · commit a20fe326e008 · 2016-05-28T03:11:52.000+02:00
diff --git a/algorithm/graph_search/dijkstra/shortest_path/code.js b/algorithm/graph_search/dijkstra/shortest_path/code.js
@@ -1,33 +1,31 @@
 function Dijkstra(start, end) {
-    var MAX_VALUE = Infinity;
     var minIndex, minDistance;
-    var S = []; // S[i] returns the distance from node v to node start
     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[i] = MAX_VALUE;
-    }
+    for (var i = 0; i < G.length; i++) D.push(false);
     S[start] = 0; // Starting node is at distance 0 from itself
     var k = G.length;
     while (k--) {
         // Finding a node with the shortest distance from S[minIndex]
         minDistance = MAX_VALUE;
         for (i = 0; i < G.length; i++) {
+            tracerS._select(i)._wait();
             if (S[i] < minDistance && !D[i]) {
                 minDistance = S[i];
                 minIndex = i;
             }
+            tracerS._deselect(i);
         }
         if (minDistance == MAX_VALUE) break; // If there is no edge from current node, jump out of loop
         D[minIndex] = true;
+        tracerS._notify(minIndex, S[minIndex])._denotify(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];
-                tracer._visit(i, minIndex, S[i])._wait();
-                tracer._leave(i, minIndex, S[i])._wait();
+                tracerS._notify(i, S[i])._wait()._denotify(i);
+                tracer._visit(i, minIndex, S[i])._wait()._leave(i, minIndex);
             }
         }
         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,12 +1,10 @@
 var tracer = new WeightedDirectedGraphTracer();
+var tracerS = new Array1DTracer();
 var logger = new LogTracer();
 tracer.attach(logger);
-/*var G = [ // G[i][j] indicates the weight of the path from the i-th node to the j-th node
- [0, 3, 0, 1, 0],
- [5, 0, 1, 2, 4],
- [1, 0, 0, 2, 0],
- [0, 2, 0, 0, 1],
- [0, 1, 3, 0, 0]
- ];*/
 var G = WeightedDirectedGraph.random(10, .4, 1, 9);
-tracer._setData(G);
+tracer._setData(G);
+var MAX_VALUE = Infinity;
+var S = []; // S[end] returns the distance from start node to end node
+for (var i = 0; i < G.length; i++) S[i] = MAX_VALUE;
+tracerS._setData(S);
