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

algorithm graph-theory floyd-warshall Java

I'm trying to implement the Floyd-Warshall algorithm in Java to detect negative cycles in a graph, but I'm consistently getting incorrect results. My implementation should identify if there are any negative weight cycles in the graph, but it seems to unexpected result in certain scenarios. Here's the snippet of my code: ```java public class FloydWarshall { private static final int INF = 99999; // A large number to represent infinity private int[][] dist; private int vertices; public FloydWarshall(int v) { this.vertices = v; dist = new int[v][v]; for (int i = 0; i < v; i++) { Arrays.fill(dist[i], INF); dist[i][i] = 0; } } public void addEdge(int u, int v, int weight) { dist[u][v] = weight; } public void floydWarshall() { for (int k = 0; k < vertices; k++) { for (int i = 0; i < vertices; i++) { for (int j = 0; j < vertices; j++) { if (dist[i][k] != INF && dist[k][j] != INF) { dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); } } } } } public boolean hasNegativeCycle() { for (int i = 0; i < vertices; i++) { if (dist[i][i] < 0) { return true; } } return false; } } ``` I initialize the distance matrix with a large number, `INF`, to signify that nodes are initially unreachable. After adding edges, I run the `floydWarshall` method and then check for negative cycles using the `hasNegativeCycle` method. The scenario occurs when I run this code with the following graph: - Vertices: 3 - Edges: (0, 1, 1), (1, 2, -1), (2, 0, -2). When I call `floydWarshall()` followed by `hasNegativeCycle()`, it returns `false` instead of `true`, even though there is a negative weight cycle. I've double-checked the edges and the weights, and they seem correct. I’m using Java 11, and I wonder if there’s something I missed in the logic or if there’s a specific edge case that I didn’t handle. Can someone guide to identify why my implementation fails to detect this negative cycle? This issue appeared after updating to Java 3.10. Thanks for taking the time to read this!