Question regarding Djisktra algorithm

Question

Regarding the point 1 , please correct me if I am wrong - I knew Djisktra fails only if there is negative weight cycle. So , it is correct , right ?

Also , under the same condition , the algorithm might fall into a infinite loop .

Comments

should ask them . Coaching have there own algorithms. both should be true . according to me .

---

@coolcoder1

Is this from made easy test series?

both are true

Answer 1

Dijkstra fails when there are negative weights and it will not go into infinite loop because Relaxation only happens E times. Bellman ford fails when there is a negative weight cycle.

Comments

How can Bellman-ford fail when there is a negative weight cycle when the iteration is only for n-1 times , u can run a loop again and check that if the distances reduce then we can say that there is a negative wght cycle but u can't say it will go into infinite loop or so .And as fas as this question is concerned Dijkstra may produce  incorrect results even if we have negative edge weights ,u can refer to this link and the dig in the answer ,no negative cycle only negative edge wght .

 

http://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm

And Dijkastra visits every vertex exactly once so whether u have a negative wght cycle or negative edge wght u will always terminate , only the fact is that u won't be getting the optimal solution ,i.e. why greedy algorithm may not give optimal solution always.There option D is correct.