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

asked in Algorithms by Boss (6k points)   | 148 views

2 Answers

+2 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 (65.2k 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.

Related questions

0 votes
1 answer
1
0 votes
1 answer
3
asked in Algorithms by radha gogia Boss (6.7k points)   | 90 views


Top Users Mar 2017
  1. rude

    5236 Points

  2. sh!va

    3054 Points

  3. Rahul Jain25

    2920 Points

  4. Kapil

    2732 Points

  5. Debashish Deka

    2602 Points

  6. 2018

    1574 Points

  7. Vignesh Sekar

    1430 Points

  8. Bikram

    1424 Points

  9. Akriti sood

    1420 Points

  10. Sanjay Sharma

    1128 Points

Monthly Topper: Rs. 500 gift card

21,549 questions
26,889 answers
61,248 comments
23,251 users