Issues with Implementing Floyd-Warshall Algorithm in C++ - Infinite Loop on Negative Cycles
I'm having trouble with I've been researching this but I'm stuck trying to Hey everyone, I'm running into an issue that's driving me crazy..... I'm currently implementing the Floyd-Warshall algorithm in C++ to calculate the shortest paths between all pairs of vertices in a weighted graph. However, I am facing an issue where my implementation seems to enter an infinite loop when there are negative weight cycles present in the graph. I am using the following code: ```cpp #include <iostream> #include <vector> #include <limits> using namespace std; const int INF = numeric_limits<int>::max(); void floydWarshall(vector<vector<int>>& graph) { int V = graph.size(); for (int k = 0; k < V; k++) { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (graph[i][k] != INF && graph[k][j] != INF) { graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]); } } } } } int main() { vector<vector<int>> graph = { {0, 5, INF, 10}, {INF, 0, 3, INF}, {INF, INF, 0, 1}, {INF, INF, INF, 0} }; // Introduce a negative cycle graph[1][0] = -4; // Edge from vertex 1 to vertex 0 floydWarshall(graph); for (const auto& row : graph) { for (const auto& val : row) { cout << (val == INF ? "INF" : to_string(val)) << " "; } cout << endl; } return 0; } ``` When I run this code with the graph that contains a negative cycle, it results in an infinite loop, and the program never completes. I've verified that the input graph is correctly set up; however, I'm not sure how to handle the negative cycles properly within the implementation. I would appreciate any insights on how to check for negative cycles effectively and modify the algorithm to prevent the infinite loop. I've read that the algorithm should be able to detect such cycles but am unsure how to integrate that feature into my current implementation. Any suggestions would be greatly appreciated! This is part of a larger web app I'm building. I'm on Ubuntu 22.04 using the latest version of C++. Any advice would be much appreciated. Is there a better approach? Any ideas what could be causing this? I'm working on a REST API that needs to handle this.