Add todo for dijkstra

mgechev · mgechev · commit 0a677cd64701 · 2014-12-04T20:01:39.000+02:00
diff --git a/src/graphs/shortest-path/dijkstra.js b/src/graphs/shortest-path/dijkstra.js
@@ -93,17 +93,22 @@ var dijstra = function () {
     var  tempDistance = 0;
     init(src, graph);
     while (current.node != dest && current.distance != Infinity) {
+      var changed = false;
       for (var i = 0; i < graph.length; i += 1) {
         if (current.node !== i && //if it's not the current node
           !visited[i] && //and if we haven't visited this node
           Number.isFinite(graph[i][current.node])) { //and this node is sibling of the current...
 
           tempDistance = current.distance + graph[i][current.node]; 
           if (tempDistance < distance[i].distance) {
+            changed = true;
             distance[i].distance = tempDistance;
           }
         }
       }
+      if (changed) {
+        // TODO the heap should update the order of the elements!
+      }
       visited[current.node] = true;
       current = unvisited.extract();
     }

Original file line number	Diff line number	Diff line change
`@@ -93,17 +93,22 @@ var dijstra = function () {`
`93`	`93`	`var tempDistance = 0;`
`94`	`94`	`init(src, graph);`
`95`	`95`	`while (current.node != dest && current.distance != Infinity) {`
	`96`	`+ var changed = false;`
`96`	`97`	`for (var i = 0; i < graph.length; i += 1) {`
`97`	`98`	`if (current.node !== i && //if it's not the current node`
`98`	`99`	`!visited[i] && //and if we haven't visited this node`
`99`	`100`	`Number.isFinite(graph[i][current.node])) { //and this node is sibling of the current...`
`100`	`101`
`101`	`102`	`tempDistance = current.distance + graph[i][current.node];`
`102`	`103`	`if (tempDistance < distance[i].distance) {`
	`104`	`+ changed = true;`
`103`	`105`	`distance[i].distance = tempDistance;`
`104`	`106`	`}`
`105`	`107`	`}`
`106`	`108`	`}`
	`109`	`+ if (changed) {`
	`110`	`+ // TODO the heap should update the order of the elements!`
	`111`	`+ }`
`107`	`112`	`visited[current.node] = true;`
`108`	`113`	`current = unvisited.extract();`
`109`	`114`	`}`