retagged by
2,919 views
0 votes
0 votes

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? 

  1. Only S1
  2. Only S2
  3. Both S1 and S2
  4. None of these
retagged by

1 Answer

1 votes
1 votes
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
Answer:

Related questions

0 votes
0 votes
1 answer
1
Vipin Rai asked Nov 11, 2018
670 views
What is the difference between Dijkstra and Bellman Ford algorithm?Will the shortest path given by both be same in following conditions :a) All positive edge weightsb) So...
1 votes
1 votes
1 answer
2
Jithin Jayan asked Jul 23, 2016
376 views
If a graph contains a positive weight cycle reachable from source, Can we find a well defined shortest path using Dijkstra/Bellman-Ford algorithm?