👀 Views: 117 💬 Answers: 1 📅 Created: 2025-06-12

python networkx algorithms Python

I'm converting an old project and Hey everyone, I'm running into an issue that's driving me crazy... I'm implementing Dijkstra's algorithm using the NetworkX library in Python, but I'm running into issues when dealing with graphs that have negative weight edges. My goal is to find the shortest path in a directed graph, but I noticed that the results are inconsistent when the graph contains negative weights. I expected Dijkstra's algorithm to throw an behavior or return None, but instead, it produces incorrect path results without any warnings. Here's a simplified version of my code: ```python import networkx as nx # Create a directed graph G = nx.DiGraph() G.add_weighted_edges_from([(1, 2, 4), (1, 3, 1), (3, 2, -2)]) # negative weight edge from 3 to 2 # Run Dijkstra's algorithm shortest_path = nx.dijkstra_path(G, source=1, target=2) print(f'Shortest path from 1 to 2: {shortest_path}') ``` I ran this code using NetworkX version 2.5.1, and it returns the path [1, 3, 2] with a total cost of 3, which is incorrect since the negative edge should have altered the path calculation. I've also tried using the `nx.single_source_dijkstra` function but received a similar result. Furthermore, I checked the documentation but couldn't find any information that indicates how Dijkstra's algorithm handles negative weights in this context. Shouldn't Dijkstra's algorithm unexpected result or give a warning when working with a negative weight edge? How can I correctly implement shortest path finding for graphs with negative weights, or is there a different algorithm I should be using? Any help would be appreciated! This is part of a larger API I'm building. I'd really appreciate any guidance on this. What am I doing wrong?