Lemma 24.15 (Path-relaxation property) Let G =(V,E)be a weighted,directed graph with weight function w:E->R. and let s e V be a source vertex.Consider any shortest path p =(vo,v1,...,v) from s=vo to vk.If G is initialized by INITIALIZE-SINGLE-SOURCE(G,s)and then a sequence of relaxation steps occurs that includes.in order.relaxing the edges (vo,v1).(v1,v2)....,(vR-1,vg).then vg.d 8(s,vg)after these relaxations and at all times afterward.This property holds no matter what other edge relaxations occur,including relaxations that are intermixed with relaxations of the edges of p. Proof We show by induction that after the ith edge of path p is relaxed,we have vi.d =8(s,vi).For the basis,i =0,and before any edges of p have been relaxed, we have from the initialization that vo.d =s.d =0=6(s,s).By the upper-bound property,the value of s.d never changes after initialization. For the inductive step,we assume that vi-1.d 6(s,vi-1),and we examine what happens when we relax edge (vi-1,vi).By the convergence property,after relaxing this edge,we have vi.d =8(s,vi),and this equality is maintained at all times thereafter. ■