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

1 votes
1 votes
I) If there is no path from S to T then Bellman Ford Algo will not return shortest path from S to T.

II) A well defined path doesn't contain a negative edge weight cycle so definitely a shortest path value (-ve or +ve) will be returned by the Bellman Ford Algorithm for the source vertex V for which shortest path is well defined. Graph G contains a negative edge weight cycle acc to question but it will not be reachable from the well defined shortest path for vertex V !!!  :) HENCE STATEMENT 2 IS TRUE
edited by
1 votes
1 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. 

0 votes
0 votes
I) For every vertex s to t , it finds shortest path . False .Because it only find shortest path from start vertex

2) No , Bellman ford algo doesnot find shortest path even if there is -ve edge weight cycle. If correct shortest path is found , it may be outside the cycle. For the cycle it alays changing value of the paths
edited by
0 votes
0 votes
Answer : False

Explanations : Statement 1 may result in negative edge weight graph, so bellman ford algorithm comes in picture. It will give 2 output. one is shortest path and second for cycle existence. so it is false.

Statement 2 :

In any case algorithm would give 1 output . If there is cycle it says about only cycle and not any path. so it is false.

Thanks.

Report me if any error is present.

Related questions

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