Interesting things coming... The upper bound is tight for Q=V-R some vertices r. 0 ▣dist(r=l(s,r). ■ Suppose we maintain a set R R of correct vertices ▣i.e.r∈R→dist(r)=l(s,r) We want to find another correct vertex u in V-R ▣ s.t.we can put u into R (and then update u's neighbors). Question:Which u to pick? 27Interesting things coming… ◼ The upper bound is tight for some vertices 𝑟. ❑ 𝑑𝑖𝑠𝑡(𝑟) = 𝑙(𝑠, 𝑟). ◼ Suppose we maintain a set 𝑅 of correct vertices ❑ i.e. 𝑟 ∈ 𝑅 ⇒ 𝑑𝑖𝑠𝑡(𝑟) = 𝑙(𝑠, 𝑟) ◼ We want to find another correct vertex 𝑢 in 𝑉 − 𝑅 ❑ s.t. we can put 𝑢 into 𝑅 (and then update 𝑢’s neighbors). ◼ Question: Which 𝑢 to pick? 𝑢 𝑠 𝑟 𝑹 𝑸 = 𝑽 − 𝑹 27