ME Test Series Question

Question

Consider the following statements given below:
S1 : If a graph contain a negative weight cycle then Dijkstra’s algorithm may or may not terminate.
S2 : Bellman Ford algorithm for every weighted graph which contain two vertices u and v always produces a shortest path.
Which of the above statements are incorrect? 

• A. Only S1
• B. Only S2
• C. Both S1 and S2
• D. None of these

Comments

Both are incorrect.

Dijkstra will always terminate , relaxation only happens once.

Bellman ford rejects graphs with negative weight cycles. So cannot produce a shortest path.

---

 

may or may not terminate. 

              always terminate 

 

weighted graph which contain two vertices u and v always produces a shortest path.

 If A graph is disconnect ?? and there is no edge between u and v ?

 

C ) both S 1 and S2

---

Right on , right on

Answer 1

both are incorrect

A)Even a graph contain negative edge weight cycle, dijkstra's algorithm will always terminate although shortest path may or may not be correct.

B)Bellman ford algorithm for weighted graph will always give correct result if there exist a path between them