1.If d(s,t)=k+1,then t E Nk+1(s) Recall:Ni(s)={all neighbors of Ni-1(s)}-Ni-1(s)-..-N(s)-{s} A shortest path from s to t has length k +1 Just before reaching t,the path reaches some t'with d(s,t')= 2 kand(t',t)∈E. S ■ By induction,t'E Nk(s).So by algorithm,t∈Nk+1(s) ..unless t∈W;(s)for some i≤ k But the bad case won't happen since otherwise d(s,t)<k by induction. 161. If 𝑑(𝑠,𝑡) = 𝑘 + 1, then 𝑡 ∈ 𝑁𝑘+1(𝑠) ◼ A shortest path from 𝑠 to 𝑡 has length 𝑘 + 1 ◼ Just before reaching 𝑡, the path reaches some 𝑡′ with 𝑑(𝑠,𝑡′) = 𝑘 and 𝑡′ ,𝑡 ∈ 𝐸. ◼ By induction, 𝑡′ ∈ 𝑁𝑘(𝑠). So by algorithm, 𝑡 ∈ 𝑁𝑘+1(𝑠) … …unless 𝑡 ∈ 𝑁𝑖(𝑠) for some 𝑖 ≤ 𝑘 ❑ But the bad case won’t happen since otherwise 𝑑 𝑠,𝑡 ≤ 𝑘 by induction. s t t’ Recall:𝑁𝑖 (𝑠) = {all neighbors of 𝑁𝑖−1 (𝑠)} − 𝑁𝑖−1 (𝑠) − ⋯ − 𝑁1 (𝑠) − {𝑠} 1 2 k 16