edited by
4,173 views
0 votes
0 votes

 

Consider the following statements

  1. For every weighted graph and any two vertices $s$ and $t$, Bellman-Ford algorithm starting at $s$ will always return the shortest path to $t$.
  2. At the termination of the Bellman-ford algorithm, even if the graph has a negative weight cycle, a correct shortest path is found for a vertex for which shortest path is well-defined.

Which of the above statements are true?

edited by

8 Answers

Best answer
5 votes
5 votes
Regarding Bellman's Ford algorithm , which is used for finding single source shortest paths where Dijkstra's Algo fails i.e. in case of negative edge weight cycle , it gives shortest path from a source to  a particular node provided it is reachable from the source .So considering this , the statement 1 is false actually since it says that between s and t we get shortest path always which is not the case [Fails in case it is not reachable from the source]

Statement 2 is true as it has mentioned the path between s and t is well defined meaning reachability is there and even if negative edge weight cycle exists , it will be handled by Bellman Ford Algo correctly.

 

Hence statement 1 is false and statement 2 is true.
selected by
6 votes
6 votes
I. For every weighted graph and any two vertices s and t, bellman Ford algorithm starting at s will always return a shortest path to t.

 Solution : FALSE. It will be true only if t is reachable from source

 
II. At the termination of the bellman Ford algorithm, even if graph has negative weight cycle, a correct shortest path is found for a vertex for which shortest path is well defined.

Solution : if there is -ve edge weight cycle and destination is reachable from source then it will throw a message like "Negative Edge Weight Cycle is There" and algorithm terminated. So i think this statement is also false.
2 votes
2 votes

A. False  If the graph contains a negative-weight cycle, then no shortest path exists for any of the vertices on this cycle and for all the vertices which have some path from source going through any vertex in this cycle. 

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.

NOTE that After the termination of Bellman Ford Algorithm. even if there is Negative-weight cycle present in the Graph, we will have Correct Shortest-path weights for those vertices for which Shortest path is well-defined in the Graph. For other vertices also, we will get some value but that won't be a correct value. 

1 votes
1 votes

Option 1 is always false.

Option 2: The keyword here is "For which shortest path is well defined.

As long as all the edge weights are non negative, the shortest-paths tree is well defined.(This is definition of well defined shortest path)

So Option 2 is True.

Related questions

1 votes
1 votes
3 answers
1
0 votes
0 votes
0 answers
4
Vaishnavi01 asked Nov 19, 2018
289 views