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

algorithms dijkstra graphs Java

I'm currently implementing Dijkstra's Algorithm in Java to find the shortest path in a weighted graph, but I'm running into issues when negative edge weights are involved. I understand that Dijkstra's algorithm is not designed to handle graphs with negative edges, but I need to ensure the implementation can gracefully handle or report such cases without crashing or providing incorrect results. Here's a snippet of my implementation: ```java import java.util.*; class Graph { private final int V; // Number of vertices private final List<List<Pair>> adj; public Graph(int v) { this.V = v; adj = new ArrayList<>(v); for (int i = 0; i < v; i++) { adj.add(new ArrayList<>()); } } public void addEdge(int u, int v, int weight) { adj.get(u).add(new Pair(v, weight)); } public void dijkstra(int src) { int[] dist = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0; PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingInt(pair -> pair.weight)); pq.offer(new Pair(src, 0)); while (!pq.isEmpty()) { Pair current = pq.poll(); int u = current.vertex; for (Pair neighbor : adj.get(u)) { int v = neighbor.vertex; int weight = neighbor.weight; if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.offer(new Pair(v, dist[v])); } } } System.out.println(Arrays.toString(dist)); } } class Pair { int vertex; int weight; Pair(int vertex, int weight) { this.vertex = vertex; this.weight = weight; } } ``` When I test the algorithm with a graph that includes a negative edge weight, like this: ```java g.addEdge(0, 1, 5); g.addEdge(1, 2, -10); g.addEdge(0, 2, 10); ``` I notice that the output does not reflect the shortest path accurately; it seems to be prioritizing the incorrect edges. Instead of handling the negative weight gracefully, it just continues calculating as if every edge was positive. What can I do to improve this implementation? Should I be implementing a separate check for negative weights before running Dijkstra's algorithm, or is there a better approach? Any insights or suggestions would be greatly appreciated.