RunestoneInteractive / RunestoneInteractive/pythonds
Diagrams are wrong for Prim's algorithm (8.22)
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 273
- Forks
- 160
- PR merge metrics
- No merged PRs in 30d
Description
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
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
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.
Assessment
- Tech stack
- python
- Domain
- documentation
- Issue type
- Bug
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 42/100