Dijkstra's Algorithm in C# - Incorrect Path Calculation with Graph Containing Negative Edge Weights
I've been banging my head against this for hours... I'm updating my dependencies and I'm currently implementing Dijkstra's algorithm in C# for a pathfinding feature in my game, but I'm encountering an issue where the calculated path seems incorrect when my graph contains negative edge weights. I understand that Dijkstra's algorithm is not suited for graphs with negative weights, but I need to handle such cases gracefully. Here's the relevant code snippet that I have written: ```csharp class Graph { private Dictionary<int, List<(int destination, int weight)>> adjList; public Graph() { 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 List<int> Dijkstra(int start) { var distances = new Dictionary<int, int>(); var priorityQueue = new SimplePriorityQueue<int>(); foreach (var vertex in adjList.Keys) { distances[vertex] = int.MaxValue; } distances[start] = 0; priorityQueue.Enqueue(start, 0); while (priorityQueue.Count > 0) { var current = priorityQueue.Dequeue(); foreach (var (destination, weight) in adjList[current]) { if (distances[current] + weight < distances[destination]) { distances[destination] = distances[current] + weight; priorityQueue.Enqueue(destination, distances[destination]); } } } return distances.Keys.ToList(); } } ``` When testing with a graph that has negative weights, like this: ```csharp Graph g = new Graph(); g.AddEdge(0, 1, 4); g.AddEdge(0, 2, -2); g.AddEdge(1, 2, 3); g.AddEdge(2, 3, 2); g.AddEdge(3, 1, -1); ``` I'm finding that the distances returned for some nodes are incorrect, and the path doesn't seem optimal. I get unexpected values like `1` returning distances of `1` instead of the correct `0`. I looked into using Bellman-Ford for graphs with negative weights, but I wanted to see if I could adapt Dijkstra's approach. Is there a way to modify my implementation to account for negative edge weights, or should I refactor this to use a different algorithm entirely? Any guidance would be greatly appreciated! What's the correct way to implement this? I'm on CentOS using the latest version of C#. I'd love to hear your thoughts on this.