👀 Views: 976 💬 Answers: 1 📅 Created: 2025-06-03

algorithm bellman-ford graph-theory Java

I just started working with I've been banging my head against this for hours. I'm working on a personal project and I'm currently implementing the Bellman-Ford algorithm in Java to find the shortest paths from a source vertex to all other vertices in a graph. However, I'm facing difficulties when it comes to handling negative weight cycles. When I test my implementation on a graph that contains these cycles, I get incorrect results or an infinite loop. Here's a simplified version of my implementation: ```java public class BellmanFord { private int[] distances; private int vertices; public BellmanFord(int vertices) { this.vertices = vertices; distances = new int[vertices]; } public void bellmanFord(int[][] graph, int source) { Arrays.fill(distances, Integer.MAX_VALUE); distances[source] = 0; for (int i = 1; i <= vertices - 1; i++) { for (int u = 0; u < vertices; u++) { for (int v = 0; v < vertices; v++) { if (graph[u][v] != 0 && distances[u] != Integer.MAX_VALUE && distances[u] + graph[u][v] < distances[v]) { distances[v] = distances[u] + graph[u][v]; } } } } } } ``` When I run this code on a graph with a negative weight cycle, I’m expecting to catch this case and print an appropriate message. Instead, I notice the distances remain unchanged after a certain number of iterations, indicating that I'm not detecting the negative cycles properly. I tried adding an additional iteration to check for updates after the main loop, but this led to an array index out of bounds error. What am I missing in my implementation to correctly detect negative weight cycles in the graph? Any recommendations on how to modify my current code or best practices to handle this scenario would be greatly appreciated. This is part of a larger CLI tool I'm building. I'd love to hear your thoughts on this.