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

asked in Algorithms by Boss (6k points)   | 186 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 (66.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 May 2017
  1. akash.dinkar12

    3338 Points

  2. pawan kumarln

    2108 Points

  3. Bikram

    1922 Points

  4. sh!va

    1682 Points

  5. Arjun

    1614 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1208 Points

  8. Angkit

    1056 Points

  9. LeenSharma

    1018 Points

  10. Arnab Bhadra

    812 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    1008 Points

  2. pawan kumarln

    734 Points

  3. Arnab Bhadra

    726 Points

  4. Arjun

    342 Points

  5. bharti

    328 Points


22,893 questions
29,196 answers
65,302 comments
27,695 users