edited by
16,458 views
49 votes
49 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$
edited by

7 Answers

Best answer
48 votes
48 votes

$\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

edited by
25 votes
25 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)
10 votes
10 votes

Dijkstra and Bellmon ford algo. have designed for weighted, connected, directed graphs.

Negative weighted cycle means effective weight of the cycle should be negative not even 0, just like the above example, it is a negative weight cycle of (-2)

So option B is correct.

7 votes
7 votes
The answer is B.
Answer:

Related questions

48 votes
48 votes
5 answers
3
Kathleen asked Sep 22, 2014
21,126 views
In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time com...