Ask Your Question

Although Networkx's is_negatively_weighted attribute is not true, why does Dijkstra's algorithm return "Contradictory paths found: negative weights?"

asked 2022-08-05 11:00:00 +0000

nofretete gravatar image

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2022-01-27 16:00:00 +0000

djk gravatar image

This error message is caused by the fact that Dijkstra's algorithm assumes that all edge weights are non-negative. If even a single edge in the input graph has a negative weight, the algorithm may produce incorrect results or even fail to terminate at all.

In some cases, the algorithm may still work correctly if the negative weights are small and only occur in specific parts of the graph. However, if there are negative cycles (i.e., loops in the graph where the sum of edge weights is negative), the algorithm will produce incorrect results or terminate with the "Contradictory paths found: negative weights" error message.

Therefore, even if the isnegativelyweighted attribute is not true, it's important to ensure that the input graph doesn't have any negative weights or cycles before running Dijkstra's algorithm.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account. This space is reserved only for answers. If you would like to engage in a discussion, please instead post a comment under the question or an answer that you would like to discuss

Add Answer

Question Tools


Asked: 2022-08-05 11:00:00 +0000

Seen: 6 times

Last updated: Jan 27 '22