👀 Views: 3 💬 Answers: 1 📅 Created: 2025-06-09

python algorithms graph-theory Python

I'm working on a project and hit a roadblock. I'm currently working on a project that requires implementing the Bellman-Ford algorithm to find the shortest paths from a source vertex in a weighted graph. However, I'm working with issues with detecting negative cycles. My implementation seems to return false negatives, indicating that no negative cycle exists even when one is present. Here's a simplified version of my code: ```python class Graph: def __init__(self, vertices): self.V = vertices # Number of vertices self.edges = [] # List to store edges def add_edge(self, u, v, w): self.edges.append((u, v, w)) # Add an edge from u to v with weight w def bellman_ford(self, src): distance = [float('inf')] * self.V distance[src] = 0 for _ in range(self.V - 1): for u, v, w in self.edges: if distance[u] != float('inf') and distance[u] + w < distance[v]: distance[v] = distance[u] + w # Check for negative-weight cycles for u, v, w in self.edges: if distance[u] != float('inf') and distance[u] + w < distance[v]: print("Graph contains negative weight cycle") return None return distance # Example usage if __name__ == '__main__': g = Graph(5) g.add_edge(0, 1, -1) g.add_edge(0, 2, 4) g.add_edge(1, 2, 3) g.add_edge(1, 3, 2) g.add_edge(1, 4, 2) g.add_edge(3, 2, 5) g.add_edge(3, 1, 1) g.add_edge(4, 3, -3) distances = g.bellman_ford(0) print(distances) ``` When I run this code, it correctly computes the shortest distances, but it fails to detect the negative cycle introduced by the edge (4, 3, -3). I've tried debugging by printing the distances after each relaxation, but I need to seem to identify where my logic is going wrong. Could someone guide to identify what might be causing this scenario? I'm using Python 3.9 and would appreciate any insights or suggestions on how to properly implement the negative cycle detection part of Bellman-Ford. I'm working with Python in a Docker container on CentOS.