Possibly counterexample to 22.2-3

[zhukovdm]

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 distance 3 for the 4th vertex. On the contrary, bfs_correct produces 2. By removing the lines we allow the algorithm to touch already queued vertices.

What do you think?

from queue import Queue

W = 0
G = 1
B = 2

class Vertex:
    def __init__(self):
        self.c = W
        self.d = float('inf')
        self.p = None

es = [ [1, 2], [3], [4], [4], [] ]

def bfs_broken():
    vs = [Vertex() for _ in range(5)]

    s = vs[0]
    # s.c = G
    s.d = 0

    Q = Queue()
    Q.put((s, 0))

    while not Q.empty():
        (vi, i) = Q.get()
        for j in es[i]:
            vj = vs[j]
            if vj.c == W:
                # vj.c = G
                vj.d = vi.d + 1
                vj.p = vi
                Q.put((vj, j))
        vi.c = B

    print(vs[4].d)

def bfs_correct():
    vs = [Vertex() for _ in range(5)]

    s = vs[0]
    s.c = G
    s.d = 0

    Q = Queue()
    Q.put((s, 0))

    while not Q.empty():
        (vi, i) = Q.get()
        for j in es[i]:
            vj = vs[j]
            if vj.c == W:
                vj.c = G
                vj.d = vi.d + 1
                vj.p = vi
                Q.put((vj, j))
        vi.c = B

    print(vs[4].d)

bfs_broken()
bfs_correct()

[zhukovdm]

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.