Difficulty Implementing Dijkstra's Algorithm in C# - Getting Incorrect Shortest Path Costs
I just started working with I've been banging my head against this for hours..... I'm currently working on an implementation of Dijkstra's Algorithm in C# using a priority queue to find the shortest path in a weighted graph. However, I'm encountering issues where the path costs seem incorrect for certain nodes, especially when there are multiple edges connecting nodes with varying weights. Here's a simplified version of my code: ```csharp using System; using System.Collections.Generic; using System.Linq; class Node { public int Id { get; set; } public List<Edge> Edges { get; set; } public Node(int id) { Id = id; Edges = new List<Edge>(); } } class Edge { public Node Destination { get; set; } public int Weight { get; set; } public Edge(Node destination, int weight) { Destination = destination; Weight = weight; } } class Graph { public List<Node> Nodes { get; set; } public Graph() { Nodes = new List<Node>(); } } public class Dijkstra { public static Dictionary<Node, int> FindShortestPaths(Graph graph, Node start) { var distances = new Dictionary<Node, int>(); var priorityQueue = new SortedSet<(int distance, Node node)>(Comparer<(int, Node)>.Create((a, b) => a.distance == b.distance ? a.node.Id - b.node.Id : a.distance - b.distance)); foreach (var node in graph.Nodes) { distances[node] = int.MaxValue; } distances[start] = 0; priorityQueue.Add((0, start)); while (priorityQueue.Any()) { var (currentDistance, currentNode) = priorityQueue.Min; priorityQueue.Remove(priorityQueue.Min); foreach (var edge in currentNode.Edges) { var newDistance = currentDistance + edge.Weight; if (newDistance < distances[edge.Destination]) { distances[edge.Destination] = newDistance; priorityQueue.Add((newDistance, edge.Destination)); } } } return distances; } } ``` I call this function like so: ```csharp var graph = new Graph(); var nodeA = new Node(1); var nodeB = new Node(2); var nodeC = new Node(3); nodeA.Edges.Add(new Edge(nodeB, 1)); nodeA.Edges.Add(new Edge(nodeC, 4)); nodeB.Edges.Add(new Edge(nodeC, 2)); graph.Nodes.Add(nodeA); graph.Nodes.Add(nodeB); graph.Nodes.Add(nodeC); var distances = Dijkstra.FindShortestPaths(graph, nodeA); ``` I'm expecting the shortest path from node A to node C to be 3 (A -> B -> C), but I get 4, which is the direct edge from A to C. I've also checked to make sure that my edges are being added correctly, and they are. Could it be an issue with how I'm managing the priority queue or possibly a logic error when updating distances? Any insights would be greatly appreciated! This is part of a larger CLI tool I'm building. What am I doing wrong? Thanks for any help you can provide! I'm using C# stable in this project. Has anyone dealt with something similar?