👀 Views: 96 💬 Answers: 1 📅 Created: 2025-07-17

java algorithms dijkstra performance Java

I'm currently implementing Dijkstra's algorithm in Java to find the shortest path in a large graph (around 100,000 nodes) using the `PriorityQueue` from the Java Collections Framework. However, I've been facing significant performance issues, and the execution time is becoming unmanageable. Here's a simplified version of my implementation: ```java import java.util.*; public class Dijkstra { static class Node { int vertex; int weight; Node(int v, int w) { vertex = v; weight = w; } } public static int dijkstra(List<List<Node>> graph, int source, int target) { int[] distances = new int[graph.size()]; Arrays.fill(distances, Integer.MAX_VALUE); distances[source] = 0; PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.weight)); pq.add(new Node(source, 0)); while (!pq.isEmpty()) { Node current = pq.poll(); if (current.vertex == target) { return distances[target]; } for (Node neighbor : graph.get(current.vertex)) { int newDist = distances[current.vertex] + neighbor.weight; if (newDist < distances[neighbor.vertex]) { distances[neighbor.vertex] = newDist; pq.add(new Node(neighbor.vertex, newDist)); } } } return -1; // Target not reachable } } ``` While this implementation works, it takes several seconds to process, and I'm concerned about scaling it up with even larger graphs. I've tried different data structures like `ArrayList` for the adjacency list and experimenting with a custom priority queue, but the performance improvements are minimal. Additionally, I noticed that the `PriorityQueue` seems to have a lot of overhead due to frequent insertions and deletions. I received some profiling results indicating that the majority of time is spent in the `poll()` and `add()` methods of `PriorityQueue`. Is there a more efficient way to implement Dijkstra's algorithm for larger graphs? Should I consider switching to a Fibonacci heap or some other advanced data structure? Any advice or suggestions for optimization would be greatly appreciated!