假设s.,u,V是s到V的一条 最短路，算法执行某轮relax V.d>=&(S,)(上界特性) 后有u.d=&(S,u) 在下一轮relax《u,v)后，有 V.d<=u.d+w(u,V)(类三角原理) V.d=&(s,) v.d<=u.d+w(u,v) =&(S,u)+w(u,V) =&(S,V) 其实，一旦v完成收敛，最短路已经形成，之后的relax已经无关S u1 u Um v.d>=&(s,v)(上界特性) 在下一轮relax(u,v)后,有 v.d<=u.d+w(u,v)(类三角原理) V v.d<=u.d+w(u,v) =&(s,u)+w(u,v) =&(s,v) S1 S2 Sj-1 Sj 其实，一旦v完成收敛，最短路已经形成,之后的relax已经无关 假设s,…,u,v是s到v的一条 最短路，算法执行某轮relax 后有u.d= &(s,u) v.d=&(s,v)