in Algorithms recategorized by
789 views
1 vote
1 vote
Is this statement correct?? and why?

.If there are negative weight cycles than dijkstra will surely fail but if there are negative weight edges(need not be cycle) then dijkstra may or may not fail.
in Algorithms recategorized by
789 views

3 Comments

Yes it's correct..
1
1
What if only one edge in the cycle is negative and the total cost(weight) of the cycle is still positive.

Is any edge present in the cycle is negative, dijkstra's will fail?
0
0
Yes, sometimes it fails for these type of cases too.
Check my comment below the given answer.
0
0

1 Answer

2 votes
2 votes
Negative weight cycle means that whenever we go through the edges of the cycle, i.e., take one cycle or more, the distance/weight to reach such vertices will reduce from earlier. Thus, for every round of the cycle the path cost is reduced, which is not true in real scenarios. This happens because a cycle allows us to go via same edges more than once.

Negative weight edges means they are not forming a cycle. Thus, we won't go through a negative edge more than once. This won't be a problem.

Djikstra algo fails with negative weight cycles but not with negative weight edges, it is because Djikstra algo can't determine if negative weight cycles are present in the graph or not. Bellman-Ford can be used in such cases.

4 Comments

@soumya, i was making it as answer and graph image is not visible again. so could you please make it as answer and again upload the pic
0
0
@Sonveer.. now it's fine ?
0
0
thank you
0
0

Related questions