Proof 证明(续) By induction of the number of enqueue EiJust after the initializing, that is the time that s ed. We can verify that the FThe inductive hypothesis is that d[v]8(s, v) hypothesis is hold here for all v EV all the time while computin 【dv在下降】 2)dv=∞≥可s, 证明(续) 证明(续) FFor the inductive step, consider a white Efrom lemma 22.1. we obtain vertex v that is discovered during the search from a vertex u. The inductive Edv=du+1≥s,u]+1≥s hypothesis implies that edul≥als,u Z: Vertex v is enqueued, and d[] never changed during the following computing thus the hypothesis is maintained Lemma 22.3 EWhen v enqueues, the last dequeued element is u, now its head V, satisfies cLet G={v12……,},v1 is the head of the du]≤dl queue, and v, is the tail, then zdv+=dv=du+1≤dH+1 dvl≤dvl+ e-dv.[u+1(by induction) dvls dvi for all i= 1, 2,-,r-1 E:Implies d[v]sd[u+1 =d[v]= d[vr+1 &Hence the enqueue operation maintains the hypothesis 55 清华大学 宋斌恒 25 Proof By induction of the number of enqueue operations. The inductive hypothesis is that d[v]≥δ(s,v) for all v ∈V all the time while computing. 【d[v]在下降】 清华大学 宋斌恒 26 证明（续） Just after the initializing, that is the time that s enqueued. We can verify that the hypothesis is hold here: 1)d[s]= 0 = δ[s,s] 2)d[v]= ∞≥ δ[s,v] 清华大学 宋斌恒 27 证明（续） For the inductive step, consider a white vertex v that is discovered during the search from a vertex u. The inductive hypothesis implies that d[u] ≥ δ[s,u]. s v u 清华大学 宋斌恒 28 证明（续） from lemma 22.1, we obtain d[v]=d[u]+1≥ δ[s,u]+1 ≥ δ[s,v] Vertex v is enqueued, and d[v] never changed during the following computing, thus the hypothesis is maintained 清华大学 宋斌恒 29 Lemma 22.3 Lemma 22.3 Let Q={v1,v2,…,vr }, v1 is the head of the queue, and vr is the tail, then: ƒ d[vr ] ≤ d[v1]+1 ƒ d[vi ] ≤ d[vi+1] for all i = 1,2,…,r-1. 清华大学 宋斌恒 30 When v enqueues, the last dequeued element is u, now its head v1 satisfies d[u]≤d[v1]. d[vr+1]=d[v]=d[u]+1 ≤d[v1]+1 d[vr ]≤d[u]+1 (by induction) Implies d[vr ] ≤d[u]+1 =d[v]= d[vr+1] Hence the enqueue operation maintains the hypothesis. s v u Q={v1 ,…, vr, v} Q={u, v1 ,…, vr}