The Gateway to Computer Science Excellence
+1 vote
347 views
When the graph contain negetive weight edges but no negetive weight cycle, in this case can dijkstra leads to incorrect result?
in Algorithms by Active (4.8k points) | 347 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.
by Veteran (118k points)
selected by
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
198,056 comments
104,682 users