Log In
1 vote
When the graph contain negetive weight edges but no negetive weight cycle, in this case can dijkstra leads to incorrect result?
in Algorithms 405 views

1 Answer

7 votes
Best answer
Why dijkastra provide wrong result for -ve edge. Because dijkastra supports increments of distance, when it goes from one vertex to other. In the middle if we get some -ve edge, this assumption will be violated. That is why dijkastra gives incorrect result for some cases.

Dijkastra doesnot check if there is a -ve edge or not. If it's assumtion is true, dijkastra even give correct result with -ve weight edges too.

selected by

Got correct Explaination , even thread was too old...

CLRS line was bit confusing and most people says it doesnt work for -ve weights.

"Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted, directed graph G D .V; E/ for the case in which all edge weights are nonnegative."

Related questions

5 votes
1 answer
What is the time complexity of Dijkstra’s algorithm if it is implemented using AVL Tree instead of Priority Queue over a graph G = (V, E)?
asked Nov 5, 2016 in Algorithms vaishali jhalani 1.2k views
1 vote
1 answer
15 votes
1 answer
For the graph given below Dijkstra’s algorithm does not provide correct shortest path tree. Suppose a new graph that is different only in weight between Q to S is created. The number of values of edge [Q to S] that ensures that Dijkstra’s provide the correct shortest path tree where the values of edge (Q to S) ∈ [–20, 20] and ‘P’ is the source vertex are ______.
asked Sep 24, 2016 in Algorithms User007 1.1k views