令 Theoren513:Forv∈T,P(v)=min{v), +WVKs v)I 令 Proof:Lets=su{v o Suppose that /'(v) is the length of a shortest path from vI to v containing only vertices in S o(1There are some paths from vi to v, but these paths don't contain the vertex v, and other vertices of t. Then l(v) is the length of the shortest path of these paths, i.e. (v)=(v) 4s(2)There are some paths from v, to v, these paths from vI to Vk don't contain other vertices of T, and the vertex Vk adjacent edge vkv. Then l(v+w(vk,v) is the length of the shortest path of these paths, viz l'(v=l(vR+w vkv).❖ Theorem 5.13: For vT‘, l’(v)= min{l(v), l(vk )+w(vk , v)} ❖ Proof: Let S'=S∪{vk }. ❖ Suppose that l‘(v) is the length of a shortest path from v1 to v containing only vertices in S’. ❖ (1)There are some paths from v1 to v, but these paths don’t contain the vertex vk and other vertices of T'. Then l(v) is the length of the shortest path of these paths, i.e. l'(v)=l(v)。 ❖ (2)There are some paths from v1 to v, these paths from v1 to vk don’t contain other vertices of T', and the vertex vk adjacent edge {vk ,v}. Then l(vk )+w(vk ,v) is the length of the shortest path of these paths, viz l'(v)= l(vk )+w(vk ,v)