Exercise 2: Negative Cycle Check on P-Q-R — Possible Solution
====================================================================

GIVEN
------------------------------
Edges: P->Q(2), Q->R(2), R->P(-5)
Source: P. Vertices: P,Q,R (V=3, so 2 normal rounds, then 1 check
round).

CYCLE WEIGHT, CHECKED DIRECTLY FIRST
------------------------------
Going all the way around P->Q->R->P: 2 + 2 + (-5) = -1

A negative total is exactly this chapter's own definition of a
negative cycle, so a negative cycle is expected here before even
running the algorithm - Bellman-Ford's extra round exists to
confirm this mechanically rather than by inspection.

ROUNDS 1 AND 2 (THE NORMAL V-1 ROUNDS)
------------------------------
Because this is a genuine negative cycle, distances keep shrinking
every time the cycle is traversed again - after the normal 2
rounds, dist = {P:-2, Q:1, R:3} (still not "final," since a true
shortest path doesn't actually exist while the cycle keeps paying
off).

EXTRA (CHECK) ROUND
------------------------------
Relax P->Q: dist[P]+2 = -2+2 = 0, which IS less than Q's current
value of 1 - this edge is STILL relaxable even after the normal
rounds finished.

RESULT
------------------------------
Yes, a negative cycle exists: P -> Q -> R -> P, with total weight
-1. Because at least one edge remained relaxable after the normal
V-1 rounds completed, per this chapter's own detection rule, no
true shortest path exists from P to the vertices on this cycle -
the "distance" could be made arbitrarily small by simply going
around the cycle more times.

WHY THIS WORKS AS AN ANSWER
------------------------------
The cycle's total weight is checked directly as a sanity check
before running the algorithm, and the extra check round is applied
exactly as this chapter's own detection rule specifies - finding a
specific edge that is still relaxable after the normal rounds,
rather than just asserting a negative cycle exists without
identifying the evidence.