Dijkstra's algorithm Initialize:dist(x)=oo for allxs,and dist(s)=0. Let Q contain all of V //Q=V-R Q=V-R ■while 0≠0 R find a u with min dist(u) uEQ S delete u from Q for each y∈N(u) /update N(u) if dist(y)>dist(u)+l(u,y) dist(y)dist(u)+l(u,y) /update the estimated upper bound 29Dijkstra’s algorithm ◼ Initialize: 𝑑𝑖𝑠𝑡(𝑥) = ∞ for all 𝑥 ≠ 𝑠, and 𝑑𝑖𝑠𝑡(𝑠) = 0. ◼ Let 𝑄 contain all of 𝑉 // 𝑄 = 𝑉 − 𝑅 ◼ while 𝑄 ≠ ∅ find a 𝑢 with min 𝑢∈𝑄 𝑑𝑖𝑠𝑡 𝑢 delete 𝑢 from 𝑄 for each 𝑦 ∈ 𝑁(𝑢) // update 𝑁(𝑢) if 𝑑𝑖𝑠𝑡(𝑦) > 𝑑𝑖𝑠𝑡(𝑢) + 𝑙(𝑢, 𝑦) 𝑑𝑖𝑠𝑡(𝑦) = 𝑑𝑖𝑠𝑡(𝑢) + 𝑙(𝑢, 𝑦) // update the estimated upper bound 𝑠 𝑢 𝑹 𝑸 = 𝑽 − 𝑹 29