Performance Issues with Dijkstra's Algorithm Implementation in C# - Incorrect Shortest Path
I've tried everything I can think of but I'm implementing Dijkstra's algorithm in C# to find the shortest path in a weighted graph, but I'm encountering performance issues and unexpected results when dealing with larger graphs... I've used a priority queue to store the nodes and their distances, but it seems that the algorithm isn't correctly updating the shortest paths. For example, in a graph with nodes represented as integers and edges as a Dictionary, I'm getting incorrect distances reported after several iterations. Here's a snippet of my current implementation: ```csharp using System; using System.Collections.Generic; using System.Linq; class Graph { private Dictionary<int, List<(int, int)>> _adjacencyList; public Graph() { _adjacencyList = new Dictionary<int, List<(int, int)>>(); } public void AddEdge(int source, int destination, int weight) { if (!_adjacencyList.ContainsKey(source)) _adjacencyList[source] = new List<(int, int)>(); _adjacencyList[source].Add((destination, weight)); } public Dictionary<int, int> Dijkstra(int start) { var distances = _adjacencyList.Keys.ToDictionary(key => key, key => int.MaxValue); distances[start] = 0; var priorityQueue = new List<(int node, int distance)>{(start, 0)}; while (priorityQueue.Count > 0) { var current = priorityQueue.OrderBy(x => x.distance).First(); priorityQueue.Remove(current); if (current.distance > distances[current.node]) continue; foreach (var neighbor in _adjacencyList[current.node]) { var newDistance = distances[current.node] + neighbor.Item2; if (newDistance < distances[neighbor.Item1]) { distances[neighbor.Item1] = newDistance; priorityQueue.Add((neighbor.Item1, newDistance)); } } } return distances; } } ``` I've tested this with a small graph and it seems to work fine. However, when I scale it up to 1000 nodes with random weights, I'm finding that the reported shortest path to some destinations is larger than expected. Additionally, the algorithm takes a noticeably longer time to complete than I anticipated. Are there any common pitfalls with Dijkstra's algorithm in C# that I could be overlooking? I suspect it might be related to how I'm managing the priority queue or updating distances. Any help would be greatly appreciated! I've been using C# for about a year now. The project is a desktop app built with C#. Am I missing something obvious?