The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 votes

Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm?

P: Always finds a negative weighted cycle, if one exists.

Q: Finds whether any negative weighted cycle is reachable from the source.

  1. $P$ only
  2. $Q$ only
  3. Both $P$ and $Q$
  4. Neither $P$ nor $Q$
asked in Algorithms by Veteran (59.5k points)
edited by | 3.1k views

3 Answers

+21 votes
Best answer

$\underline{\text{Bellman-ford Algorithm}}$

Single source shortest Path $O(VE)$

Relax every edge once in each iteration

$E \times \underbrace{(V-1)} = E.V-E = O(V.E)$

            at max $(V-1)$ edges can be there


As we can see that the last step is the verification step. In that step, values remained unchanged. If there was a negative edge weight cycle reachable from source, then at verification step also, those values will be different from the values above.

In case the cycle is not reachable from source then we can see that they will be at $\infty$ distance(or cost) from the source from the beginning till the last step. As take anything away from the $\infty$ it will still be infinite.

But it can also be the case that there are some points which are not forming a cycle and are still unreachable from source, those also will be at $\infty$ distance from the source from the beginning till end.

Hence, we won't be able to make a distinction among the cycle and such vertices. Thus, we say that this algorithm can detect negative edge weight cycles only if they are reachable from the source.

Answer is option B

answered by Boss (30.7k points)
edited by
Though answer is correct, but iterations in this given example are not correct. in each iteration it covers all edges not only the adjacent ones!
it is directed graph . then where wrong step done ? point that. which step.

@Anirudh look at the line# 3 of the algorithm, in this algorithm first we do n-1 iterations in which we consider all edges, they don't consider adjacent edges only. and at the end we do one more itertion to know if costs still change.

May be he used any other algo than what ur follow.
this algo is direclty copied from coreman! no chances of mistake!!!
Vijay where i said that ur algo is wrong . i said he use somthing other algo.

But sir given graph contains negative value not negative weight cycle.

How option q is true? How it will find any negative weighted cycle. What if a negative weighted cycle is present but unreachable from source vertex.
+8 votes
Bellman Ford algorithm Find negative weight cycle only when its is reachable from the source vertex. If the Negative weight cycle is disconnected from the source vertices then its constituent vertices are with remain infinite weight till the end iteration of the algotithm. So that negative weitht weight cycle is not detected by the Bellman Ford algorithm. So the correct option is B(Q only)
answered by Active (2.5k points)
+7 votes
The answer is B.
answered by Boss (19.7k points)
Can you explain why?
those vertices won't change from $\infty$ to any other value. To detect a cycle we see at verification step which values are still changing

Related questions

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

38,112 questions
45,619 answers
49,297 users