当我们有u.d这么一个预估值后，v.d这个预估值必须小于u.d+w(u,v)(三角不等式) 如果relaxl时不小于，修正v.d为u.d+w(u,) 修正后的v.d满足三角不等式的可能性大大提高
s u v 当我们有u.d这么一个预估值后，v.d这个预估值必须小于u.d+w(u,v)(三角不等式), 如果relax时不小于，修正v.d为u.d+w(u,v) 修正后的v.d满足三角不等式的可能性大大提高
Lemma 24.10(Triangle inequality) Let G=(V,E)be a weighted,directed graph with weight function w:ER and source vertex s.Then,for all edges (u,v)E,we have 8s,)≤8s,0)+w(u,). Prof Suppose that pis a shortest pat from sourcesto vertexv.Then p has no more weight than any other path fromsto.Specifically,path phas no more weight than the particular path that takes a shortest path from soucestovertex and then takes edge ()