GATE CS 2009 Q13 — Shortest Paths (Dijkstra, Bellman-Ford)

To determine the correctness of the statements, let us analyze how the Bellman-Ford algorithm operates:

• Statement P: "Always finds a negative weighted cycle, if one exists."
  This statement is incorrect. The Bellman-Ford algorithm is a single-source shortest path algorithm. It computes distances starting from a designated source vertex $s$. If a negative-weight cycle exists in a component of the graph that is completely unreachable from the source $s$, the distance estimates for the vertices in that cycle remain at infinity ($\infty$). Consequently, the algorithm cannot detect this cycle because no relaxations occur along its edges.
• Statement Q: "Finds whether any negative weighted cycle is reachable from the source."
  This statement is correct. If a negative-weight cycle is reachable from the source $s$, we can keep traversing the cycle to infinitely decrease the path cost. The algorithm runs relaxation for $|V|-1$ iterations. On the $|V|$-th iteration, if any edge $(u, v)$ satisfies $d[u] + w(u, v) < d[v]$, it indicates that a shorter path has been found, which is only possible if there is a negative-weight cycle reachable from the source.

Thus, only statement $Q$ is correct.