The Gateway to Computer Science Excellence

+30 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.

- $P$ only
- $Q$ only
- Both $P$ and $Q$
- Neither $P$ nor $Q$

+32 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

$$\begin{array}{|l|l|l|l|l|}\hline & \textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} \\\hline & \text{0} & \text{$\infty$} &\text{$\infty$} & \text{$\infty$}\\ &\text{null} & \text{null} & \text{null} & \text{null}\\\hline \text{i=0}&\text{0} & \text{50} & \text{70} & \text{$\infty$}\\ & \text{X} & \text{A} & \text{A} & \text{X}\\\hline \text{i=1} & \text{0} & \text{2} & \text{70} & \text{53} \\ & \text{X} & \text{C} & \text{A} & \text{B}\\\hline \text{i=2} & \text{0} & \text{2} & \text{70} & \text{5} \\ & \text{X} & \text{C} & \text{A} & \text{B}\\\hline \text{i=3} & \text{0} & \text{2} & \text{70} & \text{5} \\ & \text{X} & \text{C} & \text{A} & \text{B}\\\hline \end{array}$$

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**

0

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!

+1

@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.

+2

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.

0

In this example there is a negative edge weight cycle right(CBC)? Also it is reachable from source.So, here Bellman ford alg should detect it right(i.e, at verification step atleast one value should differ from step at i=2), that didn't happen here. It means this alg failed to detect negative edge weight cycle which is reachable from source. Please correct me if I am wrong

+1

I can't understand one thing..it might be silly..

Statement Q says that Bellman ford can find whether any negative weighted cycle is reachable from source or not.

But all the answers here are explaining that Bellman ford can find negative weighted cycle if it is reachable from source. I mean our task is to find if the algo can determine whether the negative cycle(if at all it exists) is connected or disconnected from source.

As this answer have nicely explained that if after the last iteration we find some vertices still at distance infinity we cannot infer whether those vertices were a part of negative cycle or not, this is what Q asks for right?

Am i misinterpreting the question/answer? Please help

Statement Q says that Bellman ford can find whether any negative weighted cycle is reachable from source or not.

But all the answers here are explaining that Bellman ford can find negative weighted cycle if it is reachable from source. I mean our task is to find if the algo can determine whether the negative cycle(if at all it exists) is connected or disconnected from source.

As this answer have nicely explained that if after the last iteration we find some vertices still at distance infinity we cannot infer whether those vertices were a part of negative cycle or not, this is what Q asks for right?

Am i misinterpreting the question/answer? Please help

0

There is no negative wt cycle in the graph..CBC is positive weight cycle here with weight 80-68 = 12 .. But answer "B" is correct. Correct me if I am wrong

0

so how Q true??

0

you have stated wrong examples. Negative edge cycle means everytime when you complete one loop, distendi decreases gradually.

In ur example, ( -1+2 ) will always increase distance by one.

+13 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)

+6 votes

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,367 answers

198,498 comments

105,267 users