selfmade

Question

Suppose we have a graph with a negative weight cycle reaching from the source. And if we try to compute shortest path using Dijkstra's algorithm which of the following is likely to happen?

A) May not find shortest path but report the presence of negative cycle

B) Algorithm never terminates may go to an infinite loop

C) Algorithm terminates

D) None

Answer 1

B option. Dijkstra algorithm does not check for the presence of negative edged cycle. In fact it assumes no edge weight is negative. If such a cycle exist and is reachable from source, the algorithm goes to an infinite loop.

Comments

Thank you sir :)

---

@Arjun Sir, How does the algorithm go into an infinite loop if the heap implementation is used?

Answer 2

Ans A)

If there is a -ve weight cycle and the graph can reach to -ve weight cycle from the source but not destination, then it will not find any shortest path.For getting a shortest path we have to reach from source to destination. From source when the graph is getting a -ve cycle and then reach the destination vertex then only we can say there exists a shortest path or not.Otherwise we cannot conclude anything.

Comments

Thank you.But Dijkstra doesn't report the presence of a negative cycle right?

---

if dijkastra sometime works for -ve weight edge or cycle,and sometimes doesnot work for it.

Then it can report too for this.

---

therefore to sove this repoting problem bellmann ford was introduced

because dijkastra algo can work well with -ve weight ' edge'    not cycles   and even it dont  report  back that

-ve weight cycle found

so  bellmann ford introduced which can report back about -ve weight cycle  but  at a cost of slower computational  time  even  when there is no -ve weight cycles

Answer 3

The answer is C. Dijkstra's Algorithm will always terminate(when the min-heap used as a priority queue becomes empty).

Moreover, the vertex set of adjacent nodes is computed only once. There might be a case that edge relaxation will be applied to a node even if it is not in the min-heap anymore which might have lead to an infinite loop if its adjacency were computed after the relaxation(remember, it was not in the min-heap when its edge was relaxed).