“一定”何时会发生 Lemma 24.14(Convergence property) Let G=(V,E)be a weighted,directed graph with weight function w:ER, let s e V be a source vertex,and let su-v be a shortest path in G for some vertices u,V.Suppose that G is initialized by INITIALIZE-SINGLE- SOURCE(G,s)and then a sequence of relaxation steps that includes the call RELAX(u,v,w)is executed on the edges of G.If u.d 8(s,u)at any time prior to the call,then v.d=(s,v)at all times after the call. Proof By the upper-bound property,if u.d=8(s,u)at some point prior to re- laxing edge (u,v),then this equality holds thereafter.In particular,after relaxing edge (u,v),we have v.d ☒ u.d+w(u,v) (by Lemma 24.13) 8(s,)+w(u,v) 8(s,v) (by Lemma 24.1). By the upper-bound property.v 8(s,v),from which we conclude that v.d(s,v),and this equality is maintained thereafter.“一定”何时会发生