The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
374 views

asked in Algorithms by Boss (6.6k points) | 374 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 (96.5k 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.

@Habib:- Well defined means that reach ability is there and cycle not exists

for 2nd :-

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.

source https://courses.csail.mit.edu/6.006/oldquizzes/solutions/q2-s2010-sol.pdf

 

 

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 (111 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.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,017 questions
36,844 answers
91,377 comments
34,721 users