Diagrams are wrong for Prim's algorithm (8.22)

[varunbpatil]

The following is the diagram for Prim's algorithm after the second iteration (i.e, node B has been removed from the priority queue and added to the MST).

The d values inside the nodes in the above diagram seem to come from adding the d value of node B to the corresponding edge weights (like in Dijkstra's algorithm)

d[D] = d[B] + 1 = 2 + 1 = 3
d[E] = d[B] + 4 = 2 + 4 = 6

which is wrong. Instead, the d values of nodes C, D and E should be just the edge weights from B.

d[C] = weight(B, E) = 1  // Was earlier 3
d[D] = weight(B, D) = 1  // Was earlier ∞
d[E] = weight(B, E) = 4  // Was earlier ∞

@bnmnetp

[bnmnetp]

No.

[varunbpatil]

No.

Hi @bnmnetp , sorry if I'm missing something obvious here. Can you please help me understand how d[E] = 6 in the diagram?

I traced the code for the graph provided in the book and the following is the trace I got. At no point does it set d[E] = 6. I'm a bit confused.

Iteration 1
    Added node A to the MST
        Setting distance from A to B = 2
        Setting distance from A to C = 3
        Priority Queue after iteration 1 = [['B', 2], ['C', 3], ['D', inf], ['E', inf], ['F', inf], ['G', inf]]
Iteration 2
    Added node B to the MST
        Setting distance from B to C = 1
        Setting distance from B to D = 1
        Setting distance from B to E = 4
        Priority Queue after iteration 2 = [['C', 1], ['D', 1], ['E', 4], ['F', inf], ['G', inf]]
Iteration 3
    Added node C to the MST
        Setting distance from C to F = 5
        Priority Queue after iteration 3 = [['D', 1], ['E', 4], ['F', 5], ['G', inf]]
Iteration 4
    Added node D to the MST
        Setting distance from D to E = 1
        Priority Queue after iteration 4 = [['E', 1], ['F', 5], ['G', inf]]
Iteration 5
    Added node E to the MST
        Setting distance from E to F = 1
        Priority Queue after iteration 5 = [['F', 1], ['G', inf]]
Iteration 6
    Added node F to the MST
        Setting distance from F to G = 1
        Priority Queue after iteration 6 = [['G', 1]]
Iteration 7
    Added node G to the MST
        Priority Queue after iteration 7 = []

[bnmnetp]

@yasinovskyy we should fix this before the print edition goes to print.

[tylerpar99]

@tylerpar99 currently working on this issue.

[yasinovskyy]

Will be fixed once I submit a PR with all the other updates. Here is the final version of the graph after running Prim's. Thanks @varunbpatil for pointing this out.