Proof We prove the invariant v.d >8(s,v)for all vertices vV 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 (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 all x 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) //Relax操作 之 8(,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. 既不会再减小，也不会增大既不会再减小，也不会增大 //Relax操作