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

python algorithms bellman-ford Python

I'm writing unit tests and I'm trying to implement the Bellman-Ford algorithm to find the shortest paths in a directed graph, but I'm running into an scenario where my algorithm goes into an infinite loop when it detects a negative weight cycle... I've followed the classic approach, but it seems I've overlooked something crucial. My implementation is based on Python 3.9, and I'm using a simple adjacency list to represent the graph. Here's the relevant part of my code: ```python class Graph: def __init__(self, vertices): self.V = vertices # Number of vertices self.graph = [] # Edges in the form of (source, destination, weight) def add_edge(self, u, v, w): self.graph.append((u, v, w)) def bellman_ford(self, src): # Step 1: Initialize distances from src to all other vertices as INFINITE dist = [float("inf")] * self.V dist[src] = 0 # Step 2: 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 # Step 3: 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 ``` When I run this code with the following graph (which includes a negative weight cycle): ```python # Create a graph given in the above diagram g = Graph(5) # Adding edges # (0, 1, -1), (0, 2, 4), (1, 2, 3), (1, 3, 2), (1, 4, 2), (3, 1, 1), (3, 4, -3) 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, 1, 1) g.add_edge(3, 4, -3) distances = g.bellman_ford(0) print(distances) # This line seems to cause the infinite loop ``` I expect the algorithm to detect the negative weight cycle and print a message, but instead, it enters an infinite loop when I test it with this graph. I’ve tried adding print statements to follow the flow of execution, but I'm unable to pinpoint where things go wrong. Any insights into why this might be happening or how to correctly handle the negative cycle detection without causing an infinite loop would be highly appreciated. Additionally, are there any best practices for structuring the graph representation or the algorithm to avoid similar pitfalls in the future? This is happening in both development and production on Linux. Has anyone else encountered this?