GATE CSE
First time here? Checkout the FAQ!
x
0 votes
230 views

asked in Algorithms by Boss (6.1k points)   | 230 views

2 Answers

+3 votes
Best answer
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.
answered by Veteran (66.6k points)  
selected by

@habib...But the algorithm returns False if it finds a single negative weight cycle.

But Bellman Ford will at least conclude whether there is a feasible shortest path between s and t after (v-1) iterations where v is the number of vertices..

Contrary to this Dijkstra's Algo will be stuck in loop there is negative edge weight cycle.
I have a doubt here...what do you mean by stuck in loop?
Dijkstra ends up with wrong solution if there is a negative weight cycle.
So in Bellman-ford.... is it like, it will say that cycle is present but also give correct distance for the vertices which are not present in the cycle?
Bellman ford algo has 2 targets. One , to report the existence of a negative Weight cycle reachable from source , 2nd , to find a well defined shortest path between two given vertices. So if -ve cycle present, in that case algo with return that -ve cycle exists , else it will return SPath from source

In this Qtn, reachability is a very imp point to choose correct option. Pls Look at gate 2009 bellman ford Qtn.
0 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
answered by (103 points)  
edited by
Statement 2 is not talking about two specific vertices s and t as in first statement hence no issue with second statement
I got your point, and edited the ans.


Top Users Jul 2017
  1. Bikram

    3782 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1832 Points

  4. joshi_nitish

    1494 Points

  5. Arnab Bhadra

    1096 Points

  6. Arjun

    1054 Points

  7. Hemant Parihar

    1050 Points

  8. Shubhanshu

    972 Points

  9. Ahwan

    876 Points

  10. akash.dinkar12

    642 Points


23,953 questions
30,895 answers
70,108 comments
29,273 users