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

dijkstra algorithm graph Java

I'm stuck trying to I'm currently working on implementing Dijkstra's algorithm to find the shortest path in a weighted graph using Java. However, I am working with an scenario where the path returned is not the shortest one when I have edges with equal weights. I have implemented the algorithm using a priority queue from the `java.util.PriorityQueue` class, but I suspect that it’s not handling nodes with equal weights correctly. Here’s a simplified version of my implementation: ```java import java.util.*; class Graph { private final Map<Integer, List<Edge>> 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 List<Integer> dijkstra(int start, int end) { Map<Integer, Integer> distances = new HashMap<>(); Map<Integer, Integer> previousNodes = new HashMap<>(); PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance)); Set<Integer> visited = new HashSet<>(); for (int node : adjacencyList.keySet()) { distances.put(node, Integer.MAX_VALUE); previousNodes.put(node, null); } distances.put(start, 0); priorityQueue.add(new Node(start, 0)); while (!priorityQueue.isEmpty()) { Node currentNode = priorityQueue.poll(); if (visited.contains(currentNode.id)) continue; visited.add(currentNode.id); for (Edge edge : adjacencyList.getOrDefault(currentNode.id, new ArrayList<>())) { if (visited.contains(edge.destination)) continue; int newDistance = distances.get(currentNode.id) + edge.weight; if (newDistance < distances.get(edge.destination)) { distances.put(edge.destination, newDistance); previousNodes.put(edge.destination, currentNode.id); priorityQueue.add(new Node(edge.destination, newDistance)); } } } return reconstructPath(previousNodes, start, end); } private List<Integer> reconstructPath(Map<Integer, Integer> previousNodes, int start, int end) { List<Integer> path = new LinkedList<>(); for (Integer at = end; at != null; at = previousNodes.get(at)) { path.add(at); } Collections.reverse(path); return path.size() > 1 && path.get(0) == start ? path : Collections.emptyList(); } } class Edge { int destination, weight; Edge(int destination, int weight) { this.destination = destination; this.weight = weight; } } class Node { int id, distance; Node(int id, int distance) { this.id = id; this.distance = distance; } } ``` I’ve tested it with a simple graph where multiple edges have an equal weight, but I keep getting incorrect paths. For example, when I run the function with the following edges: - (1, 2, 1) - (1, 3, 1) - (2, 4, 1) - (3, 4, 1) I expect the shortest path from 1 to 4 to be [1, 2, 4] or [1, 3, 4], but I sometimes get a path that does not reflect this, or it returns an empty list. I would appreciate any insights into what might be going wrong. Is there something I need to change in how I handle nodes with equal weights, or am I missing something in my path reconstruction logic? Hoping someone can shed some light on this. What would be the recommended way to handle this?