Unexpected Infinite Loop in Floyd-Warshall Algorithm Implementation in Java
I'm following best practices but I'm prototyping a solution and I've tried everything I can think of but I’m currently implementing the Floyd-Warshall algorithm in Java for finding the shortest paths in a weighted graph. However, I’m encountering an unexpected infinite loop when dealing with certain edge cases, specifically when the graph contains cycles. Here’s a simplified version of my code: ```java public class FloydWarshall { public static void floydWarshall(int[][] graph) { int V = graph.length; int[][] dist = new int[V][V]; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i][j] = graph[i][j]; } } for (int k = 0; k < V; k++) { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } } } } ``` I initialize the distance matrix from the input graph, but when I run the algorithm on a graph with a cycle (e.g., a triangle with edges of varying weights), it seems to enter an infinite loop. I've checked for cycles in my input graph before invoking the function, and I’m sure that the input is valid. Here’s an example graph input: ```java int[][] graph = { { 0, 3, INF }, { INF, 0, 2 }, { 1, INF, 0 } }; ``` This graph represents a cycle from vertex 2 to vertex 0 with edge weight 1. I've tried adding debug print statements at various parts of the code, but it seems like the loops are functioning correctly in terms of iteration. I’m using Java 11 and have confirmed that there are no other threads that might be interfering with the execution. Any insights on what might be causing this infinite loop or how to handle cycles more effectively would be greatly appreciated. I'd really appreciate any guidance on this. Any pointers in the right direction? My development environment is Linux. Thanks in advance!