# Dijkstra's Agorithm

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

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
0

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

1
1.2k views
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)?
1 vote
2
950 views
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????
1 vote
3
261 views