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

asked in Algorithms by Boss (6.1k points)   | 291 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 (76.3k 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 Sep 2017
  1. Habibkhan

    6362 Points

  2. Warrior

    2234 Points

  3. Arjun

    2212 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1716 Points

  8. makhdoom ghaya

    1660 Points

  9. A_i_$_h

    1528 Points

  10. rishu_darkshadow

    1512 Points


25,988 questions
33,561 answers
79,406 comments
31,026 users