Exercises — Bellman-Ford algorithm — DP approach, negative cycles detection, O(VE)

(b). Dijkstra's Algorithm is safe whenever every weight is $\ge 0$, because its greedy "once finalized, never beaten" promise holds. A single negative weight can make a longer-hop route cheaper later, breaking that promise — so (b) needs Bellman-Ford. (a) and (c) are non-negative → Dijkstra is fine (and faster).

Compute with $V-1=5$ passes. Then one extra detection pass → $6$ total passes. Mnemonic from the parent: "V-minus-one to relax, one more to react."

False. It only detects negative cycles ==reachable from the source $s$==. A negative cycle sitting in a component you can't reach from $s$ stays invisible. (Fix: add a virtual source with $0$-weight edges to every vertex.)

Init: $[0,\infty ,\infty ,\infty ]$. Pass 1 (order as listed):

• $0\to 1(6)$: $0+6<\infty \Rightarrow \text{dist}[1]=6$
• $0\to 2(7)$: $0+7<\infty \Rightarrow \text{dist}[2]=7$
• $1\to 2(-4)$: $6-4=2<7\Rightarrow \text{dist}[2]=2$
• $1\to 3(5)$: $6+5=11<\infty \Rightarrow \text{dist}[3]=11$
• $2\to 3(3)$: $2+3=5<11\Rightarrow \text{dist}[3]=5$ End of pass 1: $[0,6,2,5]$. Pass 2: every edge — nothing improves. Early-exit break. Answer: $\boxed{[0,6,2,5]}$. Notice the good edge order let it converge in one pass.

Init: $[0,\infty ,\infty ,\infty ]$. Pass 1 (reverse order):

• $2\to 3$: $\text{dist}[2]=\infty$ → skip (guard).
• $1\to 3$: $\text{dist}[1]=\infty$ → skip.
• $1\to 2$: $\text{dist}[1]=\infty$ → skip.
• $0\to 2(7)$: $\text{dist}[2]=7$.
• $0\to 1(6)$: $\text{dist}[1]=6$. End pass 1: $[0,6,7,\infty ]$. Pass 2:
• $2\to 3(3)$: $7+3=10\Rightarrow \text{dist}[3]=10$.
• $1\to 3(5)$: $6+5=11$, not $<10$ → no.
• $1\to 2(-4)$: $6-4=2<7\Rightarrow \text{dist}[2]=2$.
• $0\to 2,0\to 1$: no change. End pass 2: $[0,6,2,10]$. Pass 3:
• $2\to 3(3)$: $2+3=5<10\Rightarrow \text{dist}[3]=5$.
• rest: no change. End pass 3: $[0,6,2,5]$. Pass 4: nothing improves → break. Answer: same final $[0,6,2,5]$ but it took 3 converging passes. Same result, more work — this is exactly why we bound by $V-1$ instead of trusting a lucky order.

Init $[0,\infty ,\infty ]$. Pass 1 (listed order): $\text{dist}[1]=2$; $1\to 2$: $2-5=-3<\infty \Rightarrow \text{dist}[2]=-3$; $0\to 2$: $4$ not $<-3$ → no. → $[0,2,-3]$. Pass 2: no change → break. Answer: $[0,2,-3]$. The negative edge $1\to 2$ makes the two-hop route ($-3$) beat the direct edge ($4$).

Add the early-exit flag: track updated during each pass; if a whole pass makes no relaxation, break. It changes no output — if nothing improved in a pass, nothing will ever improve again (the array is a fixed point of the relax operator), so the remaining $V-1$-bounded passes are wasted work. This is the Graph Relaxation fixed-point argument.

With no negative cycle, some shortest path to $v$ is simple (repeating a vertex would only add a cycle; a non-negative cycle never helps, a negative one is banned). A simple path visits at most $V$ vertices → at most $V-1$ edges. So an optimal path fits inside "$\le V-1$ edges", meaning $D[V-1][v]$ already sees it. If we allowed revisiting vertices, a negative cycle could let paths use unboundedly many edges to keep dropping — then no finite $k$ suffices, and $D[k][v]\to -\infty$. This is why detection matters: it certifies that the "simple path" assumption held.

Compute phase = $(V-1)$ passes $\times E$ edges $=(4-1)\times 5=15$ relax operations. General cost $O(V\cdot E)$. (The detection pass adds one more $E=5$, giving $20$ total examinations, but the asymptotic cost stays $O(VE)$.)

The cycle $1\to 2\to 3\to 1$ has weight $2+(-6)+1=-3<0$, and it's reachable from $0$ via $0\to 1$. So yes. Trace (listed order, guarded):

• Init $[0,\infty ,\infty ,\infty ]$.
• Pass 1: $0\to 1$:$1$; $1\to 2$:$3$; $2\to 3$:$3-6=-3$; $3\to 1$:$-3+1=-2<1\Rightarrow \text{dist}[1]=-2$. → $[0,-2,3,-3]$.
• Pass 2: $1\to 2$:$-2+2=0<3\Rightarrow 0$; $2\to 3$:$0-6=-6<-3\Rightarrow -6$; $3\to 1$:$-6+1=-5<-2\Rightarrow -5$. → $[0,-5,0,-6]$.
• Pass 3 ($V-1=3$): keeps dropping, e.g. $\text{dist}[1]$ falls further.
• Detection pass (4th): some edge (e.g. $3\to 1$) still relaxes → report negative cycle. Distances are meaningless; return the flag, not numbers.

Add a virtual source $s^{\star }$ with a $0$-weight edge to every vertex ($s^{\star }\to 0,1,2,3$, all weight $0$). Now $\text{dist}[s^{\star }]=0$ makes every vertex reachable, so the cycle $2\to 3\to 2$ (weight $-2+1=-1<0$) becomes reachable and the extra detection pass catches it. Run Bellman-Ford from $s^{\star }$ on $V+1$ vertices. This is the standard "add super-source" trick and underlies Floyd-Warshall-style global checks.

Keep a parent[] array updated on every successful relax: when $(u,v)$ relaxes, set parent[v]=u. When the detection pass relaxes some edge $(u,v)$:

1. Let $x=v$. Walk x = parent[x] exactly $V$ times. This guarantees $x$ lands inside the cycle (any node reached after $V$ parent-hops must be on a cycle, since a simple chain has $<V$ edges).
2. From this $x$, follow parent links, collecting vertices until you return to $x$ again. That collected loop is the negative cycle; reverse it for forward order. Termination: step 1 is a fixed $V$ hops. Step 2 follows parent pointers around a finite cycle → returns to $x$ in $\le V$ steps. Correctness: the extra relax means $x$ lies on a chain whose weight kept dropping, which can only happen along a negative cycle.

New sizes: $V^{\prime }=V+E$, $E^{\prime }=2E$. Cost $O(V^{\prime }{E}^{\prime })=O((V+E)\cdot 2E)=O(VE+E^2)$. For dense graphs where $E=\Theta (V^2)$ this is $O(V^4)$ — much worse. Detected cycles are unchanged: each subdivided edge preserves total weight ($w+0=w$), so every cycle's sign is identical; a cycle is negative before iff negative after. Lesson: subdivision is semantically free but computationally costly — never inflate $V$ or $E$ without reason. (Contrast with SPFA, which optimizes the constant, not the asymptotics.)

Cycle weight $=3+t+(-4)=t-1$. Negative cycle $⟺t-1<0⟺\boxed{t<1}$.

• $t<1$: weight $<0$ → detection fires, no finite distances.
• $t=1$: weight $=0$ → looping neither helps nor hurts; distances are finite ($[0,3,4]$), no report.
• $t>1$: weight $>0$ → normal finite distances, no report. This is exactly the boundary the Shortest Path Problem cares about: the sign of the total cycle weight, computed by summing edges around the loop.

Cover the solutions; re-derive L2.1, L4.1, and L5.3 from scratch. If all three match, you own the relax rule, detection, and the cycle-sign threshold.