Lemma 24.11 (Upper-bound property) Let G=(V,E)be a weighted,directed graph with weight function w:E-R. Let s V be the source vertex,and let the graph be initialized by INITIALIZE- SINGLE-SOURCE(G,s).Then,v.d 8(s,v)for all vV,and this invariant is maintained over any sequence of relaxation steps on the edges of G.Moreover, once v.d achieves its lower bound 8(s,v),it never changes. Proof We prove the invariant v.d 8(s,v)for all vertices v e V by induction over the number of relaxation steps. For the basis,v.d>8(s,v)is certainly true after initialization,since v.d=oo implies v.d 8(s,v)for all v V-fs.and since s.d =0>8(s,s)(note that 8(s,s)=-oo if s is on a negative-weight cycle and 0 otherwise). For the inductive step,consider the relaxation of an edge (u,v).By the inductive hypothesis,x.d >8(s,x)for allx E V prior to the relaxation.The only d value that may change is v.d.If it changes,we have v.d u.d+w(u,v) 8(s,u)+w(u,v)(by the inductive hypothesis) ≥8(s,v) (by the triangle inequality), and so the invariant is maintained. To see that the value of v.d never changes once v.d =8(s,v),note that having achieved its lower bound,v.d cannot decrease because we have just shown that v.d 8(s,v),and it cannot increase because relaxation steps do not increase d values. ■ 既不会再减小，也不会增大。既不会再减小，也不会增大