Encountering Infinite Loop in Dijkstra's Algorithm Implementation in Java - Priority Queue Mismanagement
After trying multiple solutions online, I still can't figure this out. I'm currently implementing Dijkstra's algorithm in Java to find the shortest path in a weighted graph, but I'm running into an infinite loop when processing the priority queue... I'm using a `PriorityQueue` to manage the nodes based on their tentative distance, but it seems like the priority queue isn't updating correctly after certain nodes are processed. Here is the relevant part of my code: ```java import java.util.*; class Node { int vertex; int distance; Node(int vertex, int distance) { this.vertex = vertex; this.distance = distance; } } public class Dijkstra { public static void main(String[] args) { int graph[][] = new int[][] { { 0, 7, 0, 0, 0, 2 }, { 7, 0, 4, 0, 0, 0 }, { 0, 4, 0, 3, 0, 0 }, { 0, 0, 3, 0, 1, 0 }, { 0, 0, 0, 1, 0, 5 }, { 2, 0, 0, 0, 5, 0 } }; dijkstra(graph, 0); } static void dijkstra(int[][] graph, int src) { int numVertices = graph.length; int[] distances = new int[numVertices]; boolean[] visited = new boolean[numVertices]; PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance)); Arrays.fill(distances, Integer.MAX_VALUE); distances[src] = 0; pq.add(new Node(src, 0)); while (!pq.isEmpty()) { Node currentNode = pq.poll(); int currentVertex = currentNode.vertex; if (visited[currentVertex]) continue; visited[currentVertex] = true; for (int neighbor = 0; neighbor < numVertices; neighbor++) { if (graph[currentVertex][neighbor] != 0) { int newDist = distances[currentVertex] + graph[currentVertex][neighbor]; if (newDist < distances[neighbor]) { distances[neighbor] = newDist; pq.add(new Node(neighbor, newDist)); } } } } System.out.println("Vertex Distance from Source:"); for (int i = 0; i < numVertices; i++) { System.out.println(i + ": " + distances[i]); } } } ``` I suspect that the issue lies in how I'm managing the priority queue or possibly how I'm checking for visited nodes. I’ve tried debugging by printing the contents of the priority queue after each iteration, and it seems to contain nodes that were already processed. However, the distances are correctly calculated. The infinite loop occurs when I attempt to add a node to the queue that has already been visited. I would appreciate any insights on how to manage the priority queue effectively in this scenario or any other potential pitfalls I might be missing. I'm working on a web app that needs to handle this. I'd be grateful for any help. Could this be a known issue?