Dijkstra's Agorithm

Question

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

Answer 1

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.

Comments

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."