单源最短路问题具有最佳子结构性 Lemma 24.1 (Subpaths of shortest paths are shortest paths) Given a weighted,directed graph G=(V.E)with weight function w:E->R, let p =(vo,v1,....vk)be a shortest path from vertex vo to vertex vk and,for any i and j such that0≤i≤j≤k,let Pij=(i,vi+l,,vi）be the subpath of p from vertex vi to vertex vj.Then,Pij is a shortest path from vi to vj. Proof If we decompose path p into vv,then we have that w(p)=w(Poi)+w(Pij)+w(pik).Now,assume that there is a path p;from vi to with weight w(p(.Then,is a path from v to vk whose weight w(poi)+w(p)+w(pjk)is less than w(p),which contradicts the assumption that p is a shortest path from vo to vk.单源最短路问题具有最佳子结构性