Shortest path

Question

I have 2 doubts below, each can be True or False?
a) Dijkstra's Algo will terminate even if there is a -ve edge or -ve cycle.
b) At the termination of Bellman Ford, even if graph has -ve cycle, a correct shortest path is found for a vertex for which shortest path is well-defined.

Answer 1

a) Dijkstra's algorithm may work for some negative weight edges but not all cases which include negative edges. Dijkstra's algorithm fails for any negative weight cycle. Negative weight cycle is a cycle in which sum of all the edges is negative. But yes it will terminate for negative edge as well as for negative edge cycle. It always terminates after |E| times relaxation happens

b)There exist no algorithm to find shortest path with a negative edge cycle. Bellmen Ford algorithm relaxes an edge (number of vertices -1) times. Hence, if the same edge can be relaxed again then it shows that negative edge cycle exist in the graph. In this case Bellmen Ford algorithm returns FALSE. Bellmen Ford algorithm deals with negative edge cycles by detecting them, whereas Dijkstra's algorithm fails.

Refer CLRS for detailed explanation

Comments

In statement 1, my doubt was regarding termination of Dijkstra's Algorithm!

---

Yes it will terminate for negative edge as well as for negative edge cycle. It always terminates after |E| times relaxation happens

---

Why it won't terminate for -ve edge cycle? I am not able to understand.

---

I have made the changes in the comment and answer. I misread your comment. Sorry :D

Answer 2

A. True. The Dijkastra's and Bellman-ford algorithms differ in how many times they relax each edge and the order in which they relax edges. Dijkstra’s algorithm relaxes each edge exactly once. The Bellman-Ford algorithm relaxes each edge $|V   - 1$ times. But Both the Algorithms will definitely terminate No Matter What.

Coming to Dijkastra's algo, It always terminates after $|E|$ relaxations and $|V |+|E|$ priority queue operations, but may produce incorrect results in case of Negative weight edges.

B. TRUE. If the shortest path is well defined, then it cannot include a cycle. Thus, the shortest path contains at most $V − 1$ edges. Running the usual $V − 1$ iterations of Bellman-Form will therefore find that path.