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. 16
1. 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
2.If t E Nk+1(s),then d(s,t)=k+1 Recall:Ni(s)={all neighbors of Ni-1(s)}-Ni-1(s)-..-Ni(s)-{s} ■d(s,t)≤k+1:Why? since t is a neighbor of some vertex t'∈Nk(s), 2 d(s,t)=k by induction. ■d(s,t)≥k+1:Why? d(s,t)won't be k since otherwise it'd have been covered by some Ni(s)with i≤k.(By induction) 17
2. If 𝑡 ∈ 𝑁𝑘+1(𝑠), then 𝑑(𝑠,𝑡) = 𝑘 + 1 ◼ 𝑑(𝑠,𝑡) ≤ 𝑘 + 1: Why? since 𝑡 is a neighbor of some vertex 𝑡′ ∈ 𝑁𝑘(𝑠), ❑ 𝑑(𝑠,𝑡′) = 𝑘 by induction. ◼ 𝑑(𝑠,𝑡) ≥ 𝑘 + 1: Why? 𝑑(𝑠,𝑡) won’t be ≤ 𝑘 since otherwise it’d have been covered by some 𝑁𝑖(𝑠) with 𝑖 ≤ 𝑘. (By induction) s t t’ 1 2 k Recall:𝑁𝑖 (𝑠) = {all neighbors of 𝑁𝑖−1 (𝑠)} − 𝑁𝑖−1 (𝑠) − ⋯ − 𝑁1 (𝑠) − {𝑠} 17
Implementation of the algorithm Queue:first in first out Basic operations: o enqueue o dequeue enqueue dequeue 18
Implementation of the algorithm ◼ Queue: first in first out. ◼ Basic operations: ❑ enqueue ❑ dequeue enqueue dequeue 18
Algorithm for st-distance Initialize:dist(s)=0;dist(u)=oo for all other u, "Q=[s] While 0 is not empty Dequeue the top element u of Q //Enqueue all neighbors v ofu that haven't been covered so far into Q,with dist function updated For all neighbors v of u,if dist(v)=oo, enqueue(v) ■ dist(v)=dist(u)+1 If t is found,then stop and output dist(t) 19
Algorithm for 𝑠𝑡-distance ◼ Initialize: 𝑑𝑖𝑠𝑡(𝑠) = 0; 𝑑𝑖𝑠𝑡(𝑢) = ∞ for all other 𝑢, ◼ 𝑄 = [𝑠] ◼ While 𝑄 is not empty ❑ Dequeue the top element 𝑢 of 𝑄 ❑ // Enqueue all neighbors 𝑣 of 𝑢 that haven’t been covered so far into 𝑄, with 𝑑𝑖𝑠𝑡 function updated For all neighbors 𝑣 of 𝑢, if 𝑑𝑖𝑠𝑡(𝑣) = ∞, ◼ enqueue(𝑣) ◼ 𝑑𝑖𝑠𝑡(𝑣) = 𝑑𝑖𝑠𝑡(𝑢) + 1 ❑ If 𝑡 is found, then stop and output 𝑑𝑖𝑠𝑡(𝑡) 19