Proof of the key property:dist(u)=l(s,u). ■Recall::dist(u)≥l(S,u). ■ Will show:dist(u)<l(s,u). R ■ Take a shortest path p from s to u X Suppose p leaves R(for 1st time) by edge (x,y). [Claim]dist(y)=l(s,y). The part of p from s to y is a shortest path to y. Any prefix of a shortest path(su)is a shortest path itself (s-y) 0 dist(x)=l(s,x)since xE R. 口 So dist(y)has been tightened to l(s,y)when x updates its neighbors So dist(u)=min dist(w)<dist(y)=l(s,y)<l(p). w∈Q y∈Q Claim part≤whole 35Proof of the key property: 𝑑𝑖𝑠𝑡(𝑢) = 𝑙(𝑠, 𝑢). ◼ Recall: 𝑑𝑖𝑠𝑡 𝑢 ≥ 𝑙(𝑠, 𝑢). ◼ Will show: 𝑑𝑖𝑠𝑡 𝑢 ≤ 𝑙(𝑠, 𝑢). ◼ Take a shortest path 𝑝 from 𝑠 to 𝑢 ◼ Suppose 𝑝 leaves 𝑅 (for 1st time) by edge (𝑥, 𝑦). ◼ [Claim] 𝑑𝑖𝑠𝑡(𝑦) = 𝑙(𝑠, 𝑦). ❑ The part of 𝑝 from 𝑠 to 𝑦 is a shortest path to 𝑦. ◼ Any prefix of a shortest path (𝑠 → 𝑢) is a shortest path itself (𝑠 → 𝑦). ❑ 𝑑𝑖𝑠𝑡(𝑥) = 𝑙(𝑠, 𝑥) since 𝑥 ∈ 𝑅. ❑ So 𝑑𝑖𝑠𝑡(𝑦) has been tightened to 𝑙(𝑠, 𝑦) when 𝑥 updates its neighbors ◼ So 𝑑𝑖𝑠𝑡 𝑢 = min 𝑤∈𝑄 𝑑𝑖𝑠𝑡 𝑤 ≤ 𝑑𝑖𝑠𝑡 𝑦 = 𝑙 𝑠, 𝑦 ≤ 𝑙(𝑝). 𝑠 𝑢 𝑥 𝑦 𝑹 𝑝 𝑸 𝑦𝑄 Claim part ≤ whole 35