Correctness(continued) nitially, d[vo]=0=8(S, vo), and d[s] is unchanged by subsequent relaxations(because of the lemma from Lecture 17 that d[v28(s,v) After I pass through E, we have dv=8(s, vu) After 2 passes through E, we have d[v2]=8(s, v2) After k passes through E, we have dlv=8(s, vk) Since g contains no negative-weight cycles, p is simple Longest simple path has≤|- I edges.□ c 2001 by Charles E Leiserson Introduction to Algorithms Dav31L18.14© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.14 Correctness (continued) v1 v1 v2 v2 v3 v3 vk vk v0 v0 … s v p: Initially, d[v0] = 0 = δ(s, v0), and d[s] is unchanged by subsequent relaxations (because of the lemma from Lecture 17 that d[v] ≥ δ(s, v)). • After 1 pass through E, we have d[v1] = δ(s, v1). • After 2 passes through E, we have d[v2] = δ(s, v2). M • After k passes through E, we have d[vk] = δ(s, vk). Since G contains no negative-weight cycles, p is simple. Longest simple path has ≤ |V| – 1 edges