Diagrams are wrong for Prim's algorithm (8.22)

Open
#99 5 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
2/5
Estimated time
1-3 hours
Newbie friendliness
42/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Stale
Tech stack
python
Domain
documentation

Research direction

Start by locating the Prim's algorithm material identified as section 8.22 and compare the diagram after the second iteration with the issue's expected d values. Update the diagram so C, D, and E show the edge weights from B rather than accumulated Dijkstra-style values. Confirm the corrected labels match the stated values and diagram state.

Written by the indexing model from the issue text.

Description

bug

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).

image

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

Dominant language
Python
Stars
273
Forks
160
No merged PRs in 30d

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from RunestoneInteractive/pythonds

All issues in RunestoneInteractive/pythonds

Similar issues

More Python issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.