Which of the following statement(s)is / are correct regarding Bellman-Ford…

2009

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

P: Always finds a negative weighted cycle, if one exist s.
Q: Finds whether any negative weighted cycle is reachable 
   from the source.

Answer: B. Q Only — Final answer: The statement that Bellman-Ford "finds whether any negative weighted cycle is reachable from the source" is correct; the statement that it…

  1. A.

    P Only

  2. B.

    Q Only

  3. C.

    Both P and Q

  4. D.

    Neither P nor Q

Attempted by 259 students.

Show answer & explanation

Correct answer: B

Final answer: The statement that Bellman-Ford "finds whether any negative weighted cycle is reachable from the source" is correct; the statement that it "always finds a negative weighted cycle, if one exists" is incorrect.

Explanation:

  • Bellman-Ford relaxes all edges V-1 times to compute shortest-path estimates from the source when no negative-weight cycle is reachable from that source.

  • After these V-1 passes, performing one more full relaxation pass: if any edge can still be relaxed, that implies there is a negative-weight cycle reachable from the source.

  • If a negative-weight cycle exists but is not reachable from the chosen source, a run of Bellman-Ford from that source will not detect it. In other words, Bellman-Ford detects reachable negative cycles, not necessarily every negative cycle in the graph.

  • Time complexity: O(VE). Use Bellman-Ford when edge weights may be negative and you need to detect negative cycles reachable from the source.

Therefore, the correct statement is that Bellman-Ford finds whether any negative-weighted cycle is reachable from the source; it does not necessarily find negative-weighted cycles that are not reachable from that source.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…