Problem of BFS Nodes collected at iteration i may have a shortest path with more than i edges. ■ dist(u),the“distance”we keep in algorithm,is only an upper bound of the real distance l(s,u). ▣i.e.dist(u)≥l(S,u. It's not necessary l(s,u)yet since we may find better route later. As a result,after iteration i,we don't know l(s,u)for u E Ni(s). though we know an upper bound of l(s,u). 26Problem of BFS ◼ Nodes collected at iteration 𝑖 may have a shortest path with more than 𝑖 edges. ◼ 𝑑𝑖𝑠𝑡(𝑢), the “distance” we keep in algorithm, is only an upper bound of the real distance 𝑙(𝑠, 𝑢). ❑ i.e. 𝑑𝑖𝑠𝑡(𝑢) ≥ 𝑙(𝑠, 𝑢). ❑ It’s not necessary 𝑙(𝑠, 𝑢) yet since we may find better route later. ◼ As a result, after iteration 𝑖, we don’t know 𝑙(𝑠, 𝑢) for 𝑢 ∈ 𝑁𝑖(𝑠). ❑ though we know an upper bound of 𝑙(𝑠, 𝑢). s 10 u 1 1 1 1 26