Unexpected Infinite Loop in Dijkstra’s Algorithm with Priority Queue in C# - How to implement?
I'm trying to figure out I'm writing unit tests and I'm implementing Dijkstra's algorithm in C# to find the shortest path in a weighted graph, but I'm running into an infinite loop when processing nodes. My priority queue seems to behave incorrectly. Here's a simplified version of my code: ```csharp using System; using System.Collections.Generic; class Graph { private Dictionary<int, List<(int, int)>> adjList = new Dictionary<int, List<(int, int)>>(); public void AddEdge(int source, int destination, int weight) { if (!adjList.ContainsKey(source)) adjList[source] = new List<(int, int)>(); adjList[source].Add((destination, weight)); } public Dictionary<int, int> Dijkstra(int start) { var distances = new Dictionary<int, int>(); var priorityQueue = new SortedSet<(int distance, int node)>(Comparer<(int, int)>.Create((x, y) => { int cmp = x.distance.CompareTo(y.distance); return cmp != 0 ? cmp : x.node.CompareTo(y.node); })); foreach (var node in adjList.Keys) { distances[node] = int.MaxValue; } distances[start] = 0; priorityQueue.Add((0, start)); while (priorityQueue.Count > 0) { var (currentDistance, currentNode) = priorityQueue.Min; priorityQueue.Remove(priorityQueue.Min); foreach (var (neighbor, weight) in adjList[currentNode]) { int newDist = currentDistance + weight; if (newDist < distances[neighbor]) { distances[neighbor] = newDist; priorityQueue.Add((newDist, neighbor)); } } } return distances; } } ``` The scenario arises when I run this with a graph that has negative weight edges. Instead of returning the correct distances, the algorithm gets exploring in an infinite loop on certain nodes. I understand that Dijkstra’s algorithm doesn’t handle negative weights well, but I’d like to ensure that my priority queue is functioning correctly regardless of edge weights. I’ve tried debugging by adding print statements, and they reveal that the priority queue is not being updated properly as nodes are revisited multiple times with shorter distances. What am I missing in the implementation? Should I be using a different data structure or modifying how I handle distance updates? Any insights on how to better manage the priority queue in this scenario would be greatly appreciated! Am I approaching this the right way? I'm coming from a different tech stack and learning C#. Any ideas how to fix this? This is happening in both development and production on CentOS. I'd love to hear your thoughts on this.