RunestoneInteractive / RunestoneInteractive/pythonds

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.

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

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

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.

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.