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

python algorithm bellman-ford graph-theory Python

I'm testing a new approach and I'm upgrading from an older version and I've been struggling with this for a few days now and could really use some help. I'm implementing the Bellman-Ford algorithm in Python to find the shortest paths from a single source vertex in a weighted graph, but I'm running into issues with certain edge cases. My implementation seems to unexpected result when there are negative weight cycles. Instead of returning an indication of the presence of a negative cycle, it incorrectly calculates the shortest paths. Here’s the code I have so far: ```python class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = [] # default dictionary def add_edge(self, u, v, w): self.graph.append((u, v, w)) def bellman_ford(self, src): dist = [float("inf")] * self.V dist[src] = 0 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]: return "Graph contains negative weight cycle" return dist ``` I tested it with the following graph: - Vertices: 5 - Edges: (0, 1, -1), (0, 2, 4), (1, 2, 3), (1, 3, 2), (1, 4, 2), (3, 1, 1), (4, 3, -3) When I run `bellman_ford(0)`, I expect it to detect a negative weight cycle due to the edges causing the cycle involving vertex 1 and 3. However, instead of indicating a negative cycle, it returns incorrect distances: `[0, -1, 2, 1, -2]`. This seems to suggest that my cycle detection logic is not functioning as intended. I've checked the conditions for updating distances and added debug print statements, but everything looks fine. Any insights into what might be going wrong or how to handle the negative cycle detection correctly? I'm using Python 3.9 and testing on a local environment. My development environment is Ubuntu. Am I missing something obvious? What would be the recommended way to handle this? I'm developing on Linux with Python. What's the correct way to implement this?