👀 Views: 82 💬 Answers: 1 📅 Created: 2025-08-27

algorithm dijkstra networkx Python

After trying multiple solutions online, I still can't figure this out. I tried several approaches but none seem to work. I'm experiencing unexpected results while implementing Dijkstra's algorithm in Python using the `networkx` library. My graph contains negative edge weights, and instead of calculating the shortest paths correctly, the algorithm seems to return incorrect values. I've tried using both `networkx`'s built-in `dijkstra_path` function and my own implementation, but the results are consistently wrong when negative weights are involved. Here's a simplified version of my graph setup and Dijkstra's implementation: ```python import networkx as nx # Create a directed graph G = nx.DiGraph() G.add_weighted_edges_from([(0, 1, 4), (0, 2, 1), (2, 1, -2)]) G.add_weighted_edges_from([(1, 3, 1), (2, 3, 5)]) # Using networkx's built-in Dijkstra's algorithm shortest_path = nx.dijkstra_path(G, source=0, target=3) shortest_distance = nx.dijkstra_path_length(G, source=0, target=3) print(f'Shortest path from 0 to 3: {shortest_path}') print(f'Shortest distance from 0 to 3: {shortest_distance}') ``` The expected shortest path from node 0 to 3 should be through node 2, with total weight 6 (0 -> 2 -> 1 -> 3). However, the output shows that the algorithm is returning a much larger distance. I also tried my own implementation of Dijkstra’s algorithm, which also produced similar results. I understand that Dijkstra's algorithm is not meant for graphs with negative edge weights, but is there a workaround or a way to get it to work correctly? Is there an alternate algorithm I should consider for this case? Any help or insights would be appreciated! What am I doing wrong? For context: I'm using Python on CentOS. Could this be a known issue? For reference, this is a production application. What would be the recommended way to handle this?