Closed zhukovdm closed 7 months ago
I have found an explanation at https://sites.math.rutgers.edu/~ajl213/CLRS/Ch22.pdf#page=4 (reachable from README). It seems that the question was mentioned in the errata. However, it may be beneficial to update the answer in this repo as well.
Hi, all!
The book (I have the 3rd edition) claims that for BFS we can
remove
lines 5 and 14 of the original algorithm and this modified procedure should produce the same result. I either found a counterexample to this statement or I should have interpreted the statement incorrectly. The current solution to this problem at https://walkccc.me/CLRS/Chap22/22.2/#222-3 does not seem correct/complete.Run the code below.
bfs_broken
produces distance3
for the 4th vertex. On the contrary,bfs_correct
produces2
. By removing the lines we allow the algorithm to touch already queued vertices.What do you think?