Confusion with Floyd-Warshall Algorithm in C++ - Infinite Loop with Certain Input Graphs
Can someone help me understand I've searched everywhere and can't find a clear answer... I'm implementing the Floyd-Warshall algorithm in C++ to find the shortest paths between all pairs of vertices. However, I'm encountering an infinite loop with certain input graphs, particularly when they contain specific combinations of edges and weights. My implementation is based on the following code: ```cpp #include <iostream> #include <vector> #include <limits> using namespace std; 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] != INT_MAX && graph[k][j] != INT_MAX) { graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]); } } } } } int main() { vector<vector<int>> graph = { {0, 3, INT_MAX, 7}, {8, 0, 2, INT_MAX}, {5, INT_MAX, 0, 1}, {2, INT_MAX, INT_MAX, 0} }; floydWarshall(graph); return 0; } ``` In the code, I initialized my graph with `INT_MAX` for edges that don't exist. However, when I test with certain combinations of input graphs (especially sparse graphs with a few edges and long distances), the algorithm doesn't return control, leading to what seems like an infinite loop. I've checked that there are no cycles in the input graph, and Iām using a graph of size 4. I suspect it might be related to how I'm handling the `INT_MAX` cases, but I'm not sure. Additionally, I noticed that the output is sometimes inconsistent when I include negative weights, which I believe should not be an issue since Iām not expecting any. Has anyone faced a similar issue with their implementation of Floyd-Warshall? Any advice on how to handle these edge cases properly would be greatly appreciated. I'm working on a application that needs to handle this. For reference, this is a production desktop app. Thanks, I really appreciate it! The project is a service built with C++. Any examples would be super helpful.