Dijkstra's Relax Step: Added a check to avoid overflow in calculating edges weights.

aalhour · aalhour · commit e32bc50f6da9 · 2015-08-01T11:59:33.000+03:00
diff --git a/Algorithms/Graphs/DijkstraShortestPaths.cs b/Algorithms/Graphs/DijkstraShortestPaths.cs
@@ -82,8 +82,10 @@ private void _dijkstra(TGraph graph, TVertex source)
                 {
                     var adjacentIndex = _nodesToIndices[edge.Destination];
                     
-                    // calculate a new possible weighted path
-                    var delta = _distances[currentIndex] + edge.Weight;
+                    // calculate a new possible weighted path if the edge weight is less than infinity
+                    var delta = Infinity;
+                    if (edge.Weight < Infinity && (Infinity - edge.Weight) > _distances[currentIndex])  // Handles overflow
+                        delta = _distances[currentIndex] + edge.Weight;
 
                     // Relax the edge
                     // if check is true, a shorter path is found from current to adjacent
