👀 Views: 69 💬 Answers: 1 📅 Created: 2025-07-23

java dijkstra algorithm Java

I'm migrating some code and This might be a silly question, but I've hit a wall trying to After trying multiple solutions online, I still can't figure this out..... I'm trying to implement Dijkstra's algorithm to find the shortest path in a weighted graph represented using an adjacency list in Java... However, when I test the algorithm on a large graph, it occasionally enters an infinite loop. Here’s the simplified version of my code: ```java import java.util.*; public class Dijkstra { private static class Node { int vertex, weight; Node(int v, int w) { vertex = v; weight = w; } } public static void dijkstra(List<List<Node>> graph, int start) { PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.weight)); int[] distances = new int[graph.size()]; Arrays.fill(distances, Integer.MAX_VALUE); distances[start] = 0; pq.add(new Node(start, 0)); while (!pq.isEmpty()) { Node current = pq.poll(); int currentVertex = current.vertex; for (Node neighbor : graph.get(currentVertex)) { int newDist = distances[currentVertex] + neighbor.weight; if (newDist < distances[neighbor.vertex]) { distances[neighbor.vertex] = newDist; pq.add(new Node(neighbor.vertex, newDist)); } } } } public static void main(String[] args) { List<List<Node>> graph = new ArrayList<>(); // Initialization of graph... dijkstra(graph, 0); } } ``` The graph is set up with around 10,000 vertices and 50,000 edges. Although I've included checks to ensure that I don't process a vertex more than once (using the priority queue), I still find that in some cases, the algorithm gets exploring. I’ve added a few print statements to trace the execution, and it appears that the `poll()` method is being called repeatedly on the same vertex, leading to unprocessed neighbors. I've tried increasing the priority queue's initial capacity and refining the distance checks, but the scenario continues. The output for some test cases is: ``` Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 10000 out of bounds for length 10000 ``` This behavior occurs sporadically when the graph size is just below a certain threshold. I'm not sure if it's a question with how I handle the graph or if there's another scenario at play. Any insights on where I might be going wrong or what I could do to debug this further would be greatly appreciated. For context: I'm using Java on Linux. Is there a better approach? This is part of a larger CLI tool I'm building. Has anyone else encountered this? This is for a microservice running on Linux. Is there a better approach? How would you solve this? Cheers for any assistance! The stack includes Java and several other technologies. My development environment is Ubuntu 22.04. I'd really appreciate any guidance on this.