👀 Views: 3 💬 Answers: 1 📅 Created: 2025-06-06

java algorithms dijkstra Java

I'm reviewing some code and I'm trying to configure Quick question that's been bugging me - I'm currently implementing Dijkstra's Algorithm to find the shortest path in a graph using Java, and I'm running into memory issues when processing large input sizes. My graph can have up to 1,000,000 nodes and 5,000,000 edges. While I initially used a priority queue to handle the vertices, I noticed significant memory consumption that leads to an `OutOfMemoryError` when the input size increases. My implementation looks like this: ```java import java.util.*; class Graph { private final int vertices; private final List<List<Edge>> adjacencyList; public Graph(int vertices) { this.vertices = vertices; adjacencyList = new ArrayList<>(vertices); for (int i = 0; i < vertices; i++) { adjacencyList.add(new ArrayList<>()); } } public void addEdge(int source, int destination, int weight) { adjacencyList.get(source).add(new Edge(destination, weight)); } public int[] dijkstra(int start) { int[] distances = new int[vertices]; boolean[] visited = new boolean[vertices]; Arrays.fill(distances, Integer.MAX_VALUE); distances[start] = 0; PriorityQueue<Vertex> pq = new PriorityQueue<>(vertices, new VertexComparator()); pq.add(new Vertex(start, 0)); while (!pq.isEmpty()) { Vertex vertex = pq.poll(); int currentVertex = vertex.node; if (visited[currentVertex]) continue; visited[currentVertex] = true; for (Edge edge : adjacencyList.get(currentVertex)) { if (!visited[edge.destination]) { int newDist = distances[currentVertex] + edge.weight; if (newDist < distances[edge.destination]) { distances[edge.destination] = newDist; pq.add(new Vertex(edge.destination, newDist)); } } } } return distances; } } class Edge { int destination; int weight; public Edge(int destination, int weight) { this.destination = destination; this.weight = weight; } } class Vertex { int node; int cost; public Vertex(int node, int cost) { this.node = node; this.cost = cost; } } class VertexComparator implements Comparator<Vertex> { @Override public int compare(Vertex v1, Vertex v2) { return Integer.compare(v1.cost, v2.cost); } } ``` I've tried increasing the Java heap size using the `-Xmx` option, but it doesn’t seem to sufficiently resolve the issue. Additionally, I noticed that using a `HashMap` for the priority queue leads to even worse performance. Are there more memory-efficient data structures or optimizations I can implement to handle such large graphs in Dijkstra's Algorithm? Any advice or best practices for managing resources in this scenario would be greatly appreciated. This is part of a larger application I'm building. Any help would be greatly appreciated!