Properties of Shortest Path 416 Corollary: Shortest paths are grown from shortest paths The length of shortest path s→pu→v is S(s, v)=8(s, m)+w(u, v) v<u,p>∈Eδ(s,v)≤δ(s,u)+w(u) Idea: Start With Upper bound 23 6 Initialize-Single-Source(G, s) 1. for each vertex vE v/G/ do dul π[v]←ML 4.ds7←0 O(v) ian williams, Spring 038 9 Properties of Shortest Path u v 1 10 9 0 2 3 4 6 s 7 5 5 7 2 x y Corollary: Shortest paths are grown from shortest paths. • The length of shortest path s ĺp u ĺ v is į(s,v) = į(s,u) + w(u,v). •  <u,v>  E į(s,v) į(s,u) + w(u,v) Brian Williams, Spring 03 11 Idea: Start With Upper Bound u v 1 10 ’ ’ 9 2 3 4 6 s 0 7 5 ’ ’ 2 x y Initialize-Single-Source(G, s) 1. for each vertex v  V[G] 2. do d[u] ĸ ’ 3. ʌ[v] ĸ NIL 4. d[s] ĸ 0 O(v) Brian Williams, Spring 03 12