Difficulty with Bellman-Ford Algorithm in Python - Handling Negative Weight Cycles
I've searched everywhere and can't find a clear answer. Quick question that's been bugging me - I'm working on a personal project and I'm implementing the Bellman-Ford algorithm in Python to find the shortest paths from a source vertex to all other vertices in a weighted graph. However, I'm running into issues when my graph contains a negative weight cycle. The algorithm should ideally detect the cycle and notify me, but I'm struggling to integrate this part of the implementation effectively. Here's a snippet of my current code where I'm attempting to check for negative weight cycles: ```python class Graph: def __init__(self, vertices): self.V = vertices # Number of vertices self.graph = [] # Default dictionary to store graph def add_edge(self, u, v, w): self.graph.append((u, v, w)) # Adding edges as (source, destination, weight) def bellman_ford(self, src): dist = [float('inf')] * self.V dist[src] = 0 # Relax edges |V| - 1 times for _ in range(self.V - 1): for u, v, w in self.graph: if dist[u] != float('inf') and dist[u] + w < dist[v]: dist[v] = dist[u] + w # Check for negative-weight cycles for u, v, w in self.graph: if dist[u] != float('inf') and dist[u] + w < dist[v]: print("Graph contains negative weight cycle") return return dist ``` I've tested this with various graphs, including one that contains a negative weight cycle, but the message "Graph contains negative weight cycle" doesn't appear as expected. Instead, it seems to return incorrect distances instead. Is there something I'm missing in the cycle detection part? Additionally, I'm using Python 3.9 and have checked that the graph is constructed correctly, as I've printed the edges before running the Bellman-Ford function. I would appreciate any advice or insights on what could be going wrong, especially regarding how the cycle detection portion is implemented. My development environment is Linux. I'd really appreciate any guidance on this. I'd really appreciate any guidance on this. For reference, this is a production CLI tool. This is for a CLI tool running on Windows 10. Any pointers in the right direction?