DijkstraSmallestPath

NourBennour · web-flow · commit 1b3b12572354 · 2020-04-19T17:01:26.000+02:00
after fixing some errors.
diff --git a/maths/DijkstraSmallestPath.js b/maths/DijkstraSmallestPath.js
@@ -1,52 +1,52 @@
+// starting at s
 function solve(graph, s) {
-  var solution = {};
+  var solutions = {};
   solutions[s] = [];
   solutions[s].dist = 0;
   
   while(true) {
-    var parent = null;
-    var nearest = null;
+    var p = null;
+    var neighbor = null;
     var dist = Infinity;
     
-
+    
     for(var n in solutions) {
       if(!solutions[n])
         continue
       var ndist = solutions[n].dist;
       var adj = graph[n];
-      //for each of its adjacent nodes...
+  
       for(var a in adj) {
-        //without a solution already...
+
         if(solutions[a])
           continue;
-        //choose nearest node with lowest *total* cost
+       
         var d = adj[a] + ndist;
         if(d < dist) {
-          //reference parent
-          parent = solutions[n];
-          nearest = a;
+   
+          p = solutions[n];
+          neighbor = a;
           dist = d;
         }
       }
     }
     
-
+    //no more solutions
     if(dist === Infinity) {
         break;
     }
-
-    solutions[nearest] = parent.concat(nearest);
-
-    solutions[nearest].dist = dist;
+    
+    //extend parent's solution path
+    solutions[neighbor] = p.concat(neighbor);
+    //extend parent's cost
+    solutions[neighbor].dist = dist;
   }
   
   return solutions;
 }
-
+//create graph
 var graph = {};
 
-\\create graph
-
 var layout = {
   'R': ['2'],
   '2': ['3','4'],
@@ -66,7 +66,6 @@ var layout = {
 }
 
 //convert uni-directional to bi-directional graph
-// needs to look like: where: { a: { b: cost of a->b }
 // var graph = {
 //     a: {e:1, b:1, g:3},
 //     b: {a:1, c:1},
@@ -100,3 +99,20 @@ for(var s in solutions) {
   if(!solutions[s]) continue;
   console.log(" -> " + s + ": [" + solutions[s].join(", ") + "]   (dist:" + solutions[s].dist + ")");
 }
+
+// From '10' to
+//  -> 2: [7, 5, 4, 2]   (dist:4)
+//  -> 3: [7, 5, 4, 3]   (dist:4)
+//  -> 4: [7, 5, 4]   (dist:3)
+//  -> 5: [7, 5]   (dist:2)
+//  -> 6: [7, 5, 4, 3, 6]   (dist:5)
+//  -> 7: [7]   (dist:1)
+//  -> 8: [7, 5, 4, 8]   (dist:4)
+//  -> 9: [7, 5, 4, 3, 13, 14, 9]   (dist:7)
+//  -> 10: []   (dist:0)
+//  -> 11: [7, 5, 11]   (dist:3)
+//  -> 12: [7, 5, 11, 12]   (dist:4)
+//  -> 13: [7, 5, 4, 3, 13]   (dist:5)
+//  -> 14: [7, 5, 4, 3, 13, 14]   (dist:6)
+//  -> 15: [7, 5, 4, 3, 6, 15]   (dist:6)
+//  -> R: [7, 5, 4, 2, R]   (dist:5)
