Bellman-Ford算法的“部分”正确性 Lemma 24.2 Let G=(V,E)be a weighted,directed graph with source s and weight func- tion w E->R,and assume that G contains no negative-weight cycles that are reachable from s.Then,after the V-1 iterations of the for loop of lines 2-4 of BELLMAN-FORD,we have v.d 8(s,v)for all vertices v that are reachable from s. Proof We prove the lemma by appealing to the path-relaxation property.Con- sider any vertex v that is reachable from s,and let p =(vo,vi,...,vk),where vo =s and vk v,be any shortest path from s to v.Because shortest paths are simple,p has at most V-1 edges,and sok-1.Each of the V-1itera- tions of the for loop of lines 2-4 relaxes all E edges.Among the edges relaxed in the ith iteration.fori=1.2.....k.is (v).By the path-relaxation property, therefore,v.d=vk.d =6(s,vk)=8(s,v). ■ 为什么？Bellman-Ford算法的“部分”正确性 为什么？