Handling Large Graphs in Python with Bellman-Ford - Why is my implementation timing out?
I'm having trouble with I'm currently working on an implementation of the Bellman-Ford algorithm to find the shortest paths from a single source in a directed graph using Python 3.10. The input graph can have up to 100,000 edges, and I noticed that my algorithm is timing out on larger datasets, particularly those with dense connections and negative weight cycles. Here's a simplified version of my implementation: ```python class Graph: def __init__(self, vertices): self.V = vertices # Number of vertices self.edges = [] # List to store the graph's edges def add_edge(self, u, v, w): self.edges.append((u, v, w)) # Add edge (u, v) with weight w def bellman_ford(self, src): dist = [float('inf')] * self.V # Initialize distances dist[src] = 0 for _ in range(self.V - 1): for u, v, w in self.edges: 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.edges: if dist[u] != float('inf') and dist[u] + w < dist[v]: print("Graph contains negative weight cycle") return None return dist ``` I've tried optimizing the loop that checks for negative cycles, but I'm unsure how much it affects performance. When I run this on a graph with dense edges, I receive a timeout error from my testing framework, and I also see significantly high memory usage. I suspect it might be due to the way I'm storing and processing edges. Is there a more efficient way to handle the Bellman-Ford algorithm for large graphs or any best practices I could implement to avoid timeouts? Additionally, could the way I'm handling negative cycles be impacting performance? Any insights would be appreciated! This is part of a larger application I'm building. What am I doing wrong? My development environment is Ubuntu. What are your experiences with this?