Difficulty Implementing Dijkstra's Algorithm for a Weighted Graph in Java - Incorrect Shortest Path Result
I'm updating my dependencies and I've been researching this but I'm stuck on something that should probably be simple. I'm currently working on implementing Dijkstra's algorithm to find the shortest path in a weighted graph using Java, but I'm working with an scenario where the calculated shortest path does not match the expected result. The graph is represented using an adjacency list, and I'm using a priority queue to manage the nodes to be processed. Here's the relevant code snippet: ```java import java.util.*; class Graph { private final Map<Integer, List<Edge>> adjacencyList; public Graph() { adjacencyList = new HashMap<>(); } public void addEdge(int source, int destination, int weight) { adjacencyList.putIfAbsent(source, new ArrayList<>()); adjacencyList.get(source).add(new Edge(destination, weight)); } public Map<Integer, Integer> dijkstra(int start) { Map<Integer, Integer> distances = new HashMap<>(); PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight)); for (int vertex : adjacencyList.keySet()) { distances.put(vertex, Integer.MAX_VALUE); } distances.put(start, 0); priorityQueue.add(new Edge(start, 0)); while (!priorityQueue.isEmpty()) { Edge currentEdge = priorityQueue.poll(); int currentVertex = currentEdge.destination; int currentWeight = currentEdge.weight; for (Edge neighbor : adjacencyList.getOrDefault(currentVertex, new ArrayList<>())) { int newWeight = currentWeight + neighbor.weight; if (newWeight < distances.get(neighbor.destination)) { distances.put(neighbor.destination, newWeight); priorityQueue.add(new Edge(neighbor.destination, newWeight)); } } } return distances; } } class Edge { int destination; int weight; public Edge(int destination, int weight) { this.destination = destination; this.weight = weight; } } ``` I am testing the algorithm with the following graph: - Vertex 0 to Vertex 1 (weight 4) - Vertex 0 to Vertex 2 (weight 1) - Vertex 2 to Vertex 1 (weight 2) - Vertex 1 to Vertex 3 (weight 1) When I call the `dijkstra(0)` method, I expect the shortest path to Vertex 3 to be 5 (0 -> 2 -> 1 -> 3), but I'm getting a distance of 6 instead. I suspect there might be an scenario with how I'm updating the distances or processing the priority queue, but I need to seem to find where I went wrong. I've also tried printing out the distances at each step to debug, and they appear to be updating correctly. Could anyone guide to identify what might be causing this incorrect calculation? I'm using Java 11 and have ensured that the priority queue is functioning as intended. Any insights would be greatly appreciated! What's the best practice here? Is there a simpler solution I'm overlooking?