Self doubt

Question

1. If there is negative edge cycle then dijkstra algorithm will give correct path or not same thing about bellman ford also?
2. Bellman ford always halts or not?

Comments

https://gateoverflow.in/214955/minimum-spanning-tree

Answer 1

Dijkstra is used for positive weight cycle. It may or may not give the correct result for a negative path but it is sure to give the correct result for the positive weights. It is a greedy algorithm. This algorithm is extensively used everywhere such as google maps.

Time complexity is $O(n^2)$

On the other hand, Bellman ford is based on Dynamic programming and it is sure to give the correct result just like every other problem which is based on DP. The main motive of using this algorithm is to handle the negative weights.

Also, if it finds a negative weight cycle then it will throw a message as a negative weight cycle found.

The time complexity of this algorithm in the worst case is $O(n^2)$.