Prims MST from Wikipedia 3c not making sense
Working through the Wiki Prims example from https://en.wikipedia.org/wiki/Prim%27s_algorithm
Get to point 3c -
Loop over the edges vw connecting v to other vertices w. For each such edge, if w still belongs to Q and vw has smaller weight than C[w], perform the following steps:
Set C[w] to the cost of edge vw Set E[w] to point to edge vw.
So, if vw < C[w] - but if C[w] is already set as "C[v] (the cheapest cost of a connection to v)" then how can any edge be less than the best available?
If I let it run I get this..
Here's what I have so far...
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>MST - Prims Algorithm Solution</title>
<style>
body { padding: 0px; margin: 0px; }
canvas {
background-image: url('./gfx/map25.png');
width: 2000px;
height: 1100px;
}
</style>
</head>
<body>
<canvas id="map"></canvas>
<script>
class Place {
constructor(name, x, y, id) {
this.id = id;
this.name = name;
this.x = x;
this.y = y;
this.edges = [];
this.C = 99999; // Wiki - the cheapest cost of a connection to v
this.E = null; // Wiki - the edge providing that cheapest connection
}
}
class Edge {
constructor(node1, node2, id) {
this.id = id;
this.node1 = node1;
this.node2 = node2;
}
get distance() {
let dx = this.node1.x - this.node2.x;
let dy = this.node1.y - this.node2.y;
return Math.sqrt( dx*dx + dy*dy );
}
}
let edges = [];
let edgeData = [{"node1":{"name":"Rougham","x":283,"y":220,"id":6},"node2":{"name":"Litcham","x":485,"y":318,"id":8}},{"node1":{"name":"Rougham","x":283,"y":220,"id":6},"node2":{"name":"Great Massingham","x":216,"y":148,"id":3}},{"node1":{"name":"Rougham","x":283,"y":220,"id":6},"node2":{"name":"Weasenham St Peter","x":383,"y":179,"id":5}},{"node1":{"name":"Rougham","x":283,"y":220,"id":6},"node2":{"name":"Castle Acre","x":260,"y":368,"id":45}},{"node1":{"name":"Rougham","x":283,"y":220,"id":6},"node2":{"name":"Gayton Thorpe","x":30,"y":273,"id":7}},{"node1":{"name":"Harpley","x":181,"y":40,"id":1},"node2":{"name":"Little Massingham","x":208,"y":104,"id":2}},{"node1":{"name":"Harpley","x":181,"y":40,"id":1},"node2":{"name":"Toftrees","x":553,"y":15,"id":47}},{"node1":{"name":"Little Massingham","x":208,"y":104,"id":2},"node2":{"name":"Great Massingham","x":216,"y":148,"id":3}},{"node1":{"name":"Weasenham St Peter","x":383,"y":179,"id":5},"node2":{"name":"West Raynham","x":498,"y":81,"id":4}},{"node1":{"name":"Toftrees","x":553,"y":15,"id":47},"node2":{"name":"West Raynham","x":498,"y":81,"id":4}},{"node1":{"name":"Toftrees","x":553,"y":15,"id":47},"node2":{"name":"Great Ryeburgh","x":708,"y":25,"id":42}},{"node1":{"name":"Great Massingham","x":216,"y":148,"id":3},"node2":{"name":"Weasenham St Peter","x":383,"y":179,"id":5}},{"node1":{"name":"Toftrees","x":553,"y":15,"id":47},"node2":{"name":"Whissonet","x":532,"y":126,"id":12}},{"node1":{"name":"Whissonet","x":532,"y":126,"id":12},"node2":{"name":"Tittleshall","x":507,"y":204,"id":9}},{"node1":{"name":"Whissonet","x":532,"y":126,"id":12},"node2":{"name":"Gateley","x":667,"y":127,"id":13}},{"node1":{"name":"Tittleshall","x":507,"y":204,"id":9},"node2":{"name":"Litcham","x":485,"y":318,"id":8}},{"node1":{"name":"Gateley","x":667,"y":127,"id":13},"node2":{"name":"Great Ryeburgh","x":708,"y":25,"id":42}},{"node1":{"name":"Mileham","x":581,"y":264,"id":10},"node2":{"name":"Litcham","x":485,"y":318,"id":8}},{"node1":{"name":"Litcham","x":485,"y":318,"id":8},"node2":{"name":"Great Dunham","x":432,"y":420,"id":31}},{"node1":{"name":"Litcham","x":485,"y":318,"id":8},"node2":{"name":"Beeston","x":559,"y":395,"id":30}},{"node1":{"name":"Litcham","x":485,"y":318,"id":8},"node2":{"name":"Longham","x":629,"y":366,"id":29}},{"node1":{"name":"Gayton Thorpe","x":30,"y":273,"id":7},"node2":{"name":"West Acre","x":141,"y":372,"id":44}},{"node1":{"name":"West Acre","x":141,"y":372,"id":44},"node2":{"name":"Narbourough","x":79,"y":440,"id":41}},{"node1":{"name":"West Acre","x":141,"y":372,"id":44},"node2":{"name":"Castle Acre","x":260,"y":368,"id":45}},{"node1":{"name":"West Acre","x":141,"y":372,"id":44},"node2":{"name":"South Acre","x":241,"y":409,"id":46}},{"node1":{"name":"South Acre","x":241,"y":409,"id":46},"node2":{"name":"Castle Acre","x":260,"y":368,"id":45}},{"node1":{"name":"Castle Acre","x":260,"y":368,"id":45},"node2":{"name":"Litcham","x":485,"y":318,"id":8}},{"node1":{"name":"South Acre","x":241,"y":409,"id":46},"node2":{"name":"Swaffham","x":266,"y":557,"id":50}},{"node1":{"name":"Swaffham","x":266,"y":557,"id":50},"node2":{"name":"Narbourough","x":79,"y":440,"id":41}},{"node1":{"name":"Swaffham","x":266,"y":557,"id":50},"node2":{"name":"Necton","x":439,"y":548,"id":43}},{"node1":{"name":"Necton","x":439,"y":548,"id":43},"node2":{"name":"Great Dunham","x":432,"y":420,"id":31}},{"node1":{"name":"Great Dunham","x":432,"y":420,"id":31},"node2":{"name":"Little Fransham","x":528,"y":486,"id":32}},{"node1":{"name":"Necton","x":439,"y":548,"id":43},"node2":{"name":"Little Fransham","x":528,"y":486,"id":32}},{"node1":{"name":"Little Fransham","x":528,"y":486,"id":32},"node2":{"name":"Beeston","x":559,"y":395,"id":30}},{"node1":{"name":"Little Fransham","x":528,"y":486,"id":32},"node2":{"name":"Scarning","x":649,"y":492,"id":33}},{"node1":{"name":"Little Fransham","x":528,"y":486,"id":32},"node2":{"name":"Longham","x":629,"y":366,"id":29}},{"node1":{"name":"Scarning","x":649,"y":492,"id":33},"node2":{"name":"Dereham","x":790,"y":462,"id":34}},{"node1":{"name":"Scarning","x":649,"y":492,"id":33},"node2":{"name":"Yaxham","x":850,"y":548,"id":35}},{"node1":{"name":"Scarning","x":649,"y":492,"id":33},"node2":{"name":"Longham","x":629,"y":366,"id":29}},{"node1":{"name":"Yaxham","x":850,"y":548,"id":35},"node2":{"name":"Mattishall","x":996,"y":540,"id":36}},{"node1":{"name":"Yaxham","x":850,"y":548,"id":35},"node2":{"name":"Dereham","x":790,"y":462,"id":34}},{"node1":{"name":"Mattishall","x":996,"y":540,"id":36},"node2":{"name":"Honingham","x":1126,"y":537,"id":38}},{"node1":{"name":"Honingham","x":1126,"y":537,"id":38},"node2":{"name":"Easton","x":1256,"y":547,"id":49}},{"node1":{"name":"Honingham","x":1126,"y":537,"id":38},"node2":{"name":"Hockering","x":1049,"y":481,"id":37}},{"node1":{"name":"Honingham","x":1126,"y":537,"id":38},"node2":{"name":"Weston Longville","x":1186,"y":409,"id":39}},{"node1":{"name":"Easton","x":1256,"y":547,"id":49},"node2":{"name":"Taverham","x":1322,"y":468,"id":40}},{"node1":{"name":"Taverham","x":1322,"y":468,"id":40},"node2":{"name":"Weston Longville","x":1186,"y":409,"id":39}},{"node1":{"name":"Taverham","x":1322,"y":468,"id":40},"node2":{"name":"Swannington","x":1218,"y":301,"id":22}},{"node1":{"name":"Taverham","x":1322,"y":468,"id":40},"node2":{"name":"Cawston","x":1262,"y":154,"id":21}},{"node1":{"name":"Cawston","x":1262,"y":154,"id":21},"node2":{"name":"Salle","x":1190,"y":135,"id":20}},{"node1":{"name":"Salle","x":1190,"y":135,"id":20},"node2":{"name":"Reepham","x":1147,"y":191,"id":19}},{"node1":{"name":"Reepham","x":1147,"y":191,"id":19},"node2":{"name":"Swannington","x":1218,"y":301,"id":22}},{"node1":{"name":"Reepham","x":1147,"y":191,"id":19},"node2":{"name":"Foxley","x":956,"y":221,"id":17}},{"node1":{"name":"Reepham","x":1147,"y":191,"id":19},"node2":{"name":"Lenwade","x":1152,"y":323,"id":23}},{"node1":{"name":"Swannington","x":1218,"y":301,"id":22},"node2":{"name":"Lenwade","x":1152,"y":323,"id":23}},{"node1":{"name":"Lenwade","x":1152,"y":323,"id":23},"node2":{"name":"Weston Longville","x":1186,"y":409,"id":39}},{"node1":{"name":"Lenwade","x":1152,"y":323,"id":23},"node2":{"name":"Taverham","x":1322,"y":468,"id":40}},{"node1":{"name":"Lenwade","x":1152,"y":323,"id":23},"node2":{"name":"Lyng","x":1044,"y":336,"id":24}},{"node1":{"name":"Reepham","x":1147,"y":191,"id":19},"node2":{"name":"Lyng","x":1044,"y":336,"id":24}},{"node1":{"name":"Lyng","x":1044,"y":336,"id":24},"node2":{"name":"Elsing","x":1026,"y":374,"id":25}},{"node1":{"name":"Elsing","x":1026,"y":374,"id":25},"node2":{"name":"Hockering","x":1049,"y":481,"id":37}},{"node1":{"name":"Hockering","x":1049,"y":481,"id":37},"node2":{"name":"Dereham","x":790,"y":462,"id":34}},{"node1":{"name":"Lenwade","x":1152,"y":323,"id":23},"node2":{"name":"Foxley","x":956,"y":221,"id":17}},{"node1":{"name":"Foxley","x":956,"y":221,"id":17},"node2":{"name":"Twyford","x":896,"y":137,"id":15}},{"node1":{"name":"Twyford","x":896,"y":137,"id":15},"node2":{"name":"Foulsham","x":947,"y":104,"id":16}},{"node1":{"name":"Foulsham","x":947,"y":104,"id":16},"node2":{"name":"Wood Norton","x":851,"y":21,"id":48}},{"node1":{"name":"Wood Norton","x":851,"y":21,"id":48},"node2":{"name":"Guist","x":831,"y":83,"id":14}},{"node1":{"name":"Guist","x":831,"y":83,"id":14},"node2":{"name":"Twyford","x":896,"y":137,"id":15}},{"node1":{"name":"Great Ryeburgh","x":708,"y":25,"id":42},"node2":{"name":"Wood Norton","x":851,"y":21,"id":48}},{"node1":{"name":"Guist","x":831,"y":83,"id":14},"node2":{"name":"Great Ryeburgh","x":708,"y":25,"id":42}},{"node1":{"name":"Guist","x":831,"y":83,"id":14},"node2":{"name":"North Elmham","x":789,"y":232,"id":18}},{"node1":{"name":"Gateley","x":667,"y":127,"id":13},"node2":{"name":"North Elmham","x":789,"y":232,"id":18}},{"node1":{"name":"North Elmham","x":789,"y":232,"id":18},"node2":{"name":"Foxley","x":956,"y":221,"id":17}},{"node1":{"name":"Foxley","x":956,"y":221,"id":17},"node2":{"name":"Swanton Morley","x":895,"y":342,"id":26}},{"node1":{"name":"Mileham","x":581,"y":264,"id":10},"node2":{"name":"East Bilney","x":681,"y":268,"id":11}},{"node1":{"name":"East Bilney","x":681,"y":268,"id":11},"node2":{"name":"Gateley","x":667,"y":127,"id":13}},{"node1":{"name":"East Bilney","x":681,"y":268,"id":11},"node2":{"name":"North Elmham","x":789,"y":232,"id":18}},{"node1":{"name":"East Bilney","x":681,"y":268,"id":11},"node2":{"name":"Beetley","x":748,"y":337,"id":28}},{"node1":{"name":"Longham","x":629,"y":366,"id":29},"node2":{"name":"Beetley","x":748,"y":337,"id":28}},{"node1":{"name":"Beetley","x":748,"y":337,"id":28},"node2":{"name":"Hoe","x":785,"y":367,"id":27}},{"node1":{"name":"Hoe","x":785,"y":367,"id":27},"node2":{"name":"North Elmham","x":789,"y":232,"id":18}},{"node1":{"name":"Hoe","x":785,"y":367,"id":27},"node2":{"name":"Dereham","x":790,"y":462,"id":34}},{"node1":{"name":"Swanton Morley","x":895,"y":342,"id":26},"node2":{"name":"Dereham","x":790,"y":462,"id":34}},{"node1":{"name":"Beeston","x":559,"y":395,"id":30},"node2":{"name":"Longham","x":629,"y":366,"id":29}},{"node1":{"name":"Weasenham St Peter","x":383,"y":179,"id":5},"node2":{"name":"Castle Acre","x":260,"y":368,"id":45}},{"node1":{"name":"Weasenham St Peter","x":383,"y":179,"id":5},"node2":{"name":"Litcham","x":485,"y":318,"id":8}}];
let places = [];
let placeData = [{"name":"Harpley","x":181,"y":40,"id":1},{"name":"Little Massingham","x":208,"y":104,"id":2},{"name":"Great Massingham","x":216,"y":148,"id":3},{"name":"West Raynham","x":498,"y":81,"id":4},{"name":"Weasenham St Peter","x":383,"y":179,"id":5},{"name":"Rougham","x":283,"y":220,"id":6},{"name":"Gayton Thorpe","x":30,"y":273,"id":7},{"name":"Litcham","x":485,"y":318,"id":8},{"name":"Tittleshall","x":507,"y":204,"id":9},{"name":"Mileham","x":581,"y":264,"id":10},{"name":"East Bilney","x":681,"y":268,"id":11},{"name":"Whissonet","x":532,"y":126,"id":12},{"name":"Gateley","x":667,"y":127,"id":13},{"name":"Guist","x":831,"y":83,"id":14},{"name":"Twyford","x":896,"y":137,"id":15},{"name":"Foulsham","x":947,"y":104,"id":16},{"name":"Foxley","x":956,"y":221,"id":17},{"name":"North Elmham","x":789,"y":232,"id":18},{"name":"Reepham","x":1147,"y":191,"id":19},{"name":"Salle","x":1190,"y":135,"id":20},{"name":"Cawston","x":1262,"y":154,"id":21},{"name":"Swannington","x":1218,"y":301,"id":22},{"name":"Lenwade","x":1152,"y":323,"id":23},{"name":"Lyng","x":1044,"y":336,"id":24},{"name":"Elsing","x":1026,"y":374,"id":25},{"name":"Swanton Morley","x":895,"y":342,"id":26},{"name":"Hoe","x":785,"y":367,"id":27},{"name":"Beetley","x":748,"y":337,"id":28},{"name":"Longham","x":629,"y":366,"id":29},{"name":"Beeston","x":559,"y":395,"id":30},{"name":"Great Dunham","x":432,"y":420,"id":31},{"name":"Little Fransham","x":528,"y":486,"id":32},{"name":"Scarning","x":649,"y":492,"id":33},{"name":"Dereham","x":790,"y":462,"id":34},{"name":"Yaxham","x":850,"y":548,"id":35},{"name":"Mattishall","x":996,"y":540,"id":36},{"name":"Hockering","x":1049,"y":481,"id":37},{"name":"Honingham","x":1126,"y":537,"id":38},{"name":"Weston Longville","x":1186,"y":409,"id":39},{"name":"Taverham","x":1322,"y":468,"id":40},{"name":"Narbourough","x":79,"y":440,"id":41},{"name":"Great Ryeburgh","x":708,"y":25,"id":42},{"name":"Necton","x":439,"y":548,"id":43},{"name":"West Acre","x":141,"y":372,"id":44},{"name":"Castle Acre","x":260,"y":368,"id":45},{"name":"South Acre","x":241,"y":409,"id":46},{"name":"Toftrees","x":553,"y":15,"id":47},{"name":"Wood Norton","x":851,"y":21,"id":48},{"name":"Easton","x":1256,"y":547,"id":49},{"name":"Swaffham","x":266,"y":557,"id":50}];
// Setup the canvas bits
const canvas = document.getElementById("map");
const ctx = canvas.getContext("2d");
canvas.width = 2000;
canvas.height = 1100;
// The forest (F) and visited list (Q)
let F = {places: [], edges: []};
let Q = [];
document.addEventListener("DOMContentLoaded", ()=> {
// Create the nodes / place instances
placeData.forEach((place)=>{
places.push(new Place(place.name, place.x, place.y, place.id));
});
// Create the edges with their nodes
edgeData.forEach((edge)=>{
edges.push(new Edge(places[edge.node1.id-1], places[edge.node2.id-1], edges.length+1 ));
});
// Update nodes with their edges
edges.forEach((edge)=>{
edge.node1.edges.push(edge);
edge.node2.edges.push(edge);
});
/**
* Wiki - Associate with each vertex v of the graph a number C[v] (the cheapest cost of a connection to v)
* and an edge E[v] (the edge providing that cheapest connection). To initialize these values, set all
* values of C[v] to +∞ (or to any number larger than the maximum edge weight) and set each E[v] to a
* special flag value indicating that there is no edge connecting v to earlier vertices.
*/
places.forEach((place)=>{
let C = 99999;
let E = null;
place.edges.forEach((edge)=>{
if(edge.distance < C) {
C = edge.distance;
E = edge;
}
});
place.C = C;
place.E = E;
});
/* Draw everything we have, places (nodes), routes (edges), E[v] (best edge), distances */
ctx.clearRect(0, 0, canvas.width, canvas.height);
drawEdges();
drawPlaceE();
drawPlaces();
drawDistances();
/**
* Wiki - Initialize an empty forest F and a set Q of vertices that have not yet been
* included in F (initially, all vertices).
*/
F = {places: [], edges: []};
places.forEach((place)=>{
Q.push(place);
});
console.log(`Step 1 : F, Q`,F ,Q);
/**
* Wiki - Repeat the following steps until Q is empty:
*/
step(1);
});
/* The Prim algorithm */
function step(n) {
for(let l = 0; l < n; l+=1) {
/**
* Wiki - Find and remove a vertex v from Q having the minimum possible value of C[v]
*/
let lowestC = 99999;
let lowestPlace = null;
let lowestIndex = 0;
Q.forEach((place, index)=>{
if(place.C < lowestC) {
lowestC = place.C;
lowestPlace = place;
lowestIndex = index;
}
});
Q.splice(lowestIndex, 1);
/**
* Wiki - Add v to F and, if E[v] is not the special flag value, also add E[v] to F
*/
F.places.push(lowestPlace);
if(lowestPlace.E !== null) {
F.edges.push(lowestPlace.E);
lowestPlace.E = null;
}
console.log(`Step end : F, Q`,F ,Q);
/* Draw the forest after this step ... */
drawF();
/**
* Wiki - Loop over the edges vw connecting v to other vertices w.
*/
/**
* Wiki - For each such edge, if w still belongs to Q and vw has
* smaller weight than C[w], perform the following steps:
*/
/**
* Wiki - Set C[w] to the cost of edge vw
* Set E[w] to point to edge vw
*/
}
}
/* Draw the F edges, the final MST */
function drawF() {
F.edges.forEach((edge)=>{
ctx.beginPath();
ctx.strokeStyle = "red";
ctx.lineWidth = 4;
ctx.moveTo(edge.node1.x, edge.node1.y);
ctx.lineTo(edge.node2.x, edge.node2.y);
ctx.stroke();
});
}
/* Draw the E (edge with lowest cost to get to the place) */
function drawPlaceE() {
places.forEach((place)=>{
ctx.beginPath();
ctx.strokeStyle = "green";
ctx.lineWidth = 2;
ctx.moveTo(place.E.node1.x, place.E.node1.y);
ctx.lineTo(place.E.node2.x, place.E.node2.y);
ctx.stroke();
});
}
/* Draw the places */
function drawPlaces() {
ctx.fillStyle = "red";
places.forEach((place)=>{
ctx.fillRect(place.x-5, place.y-5, 10, 10);
});
}
/* Draw the edges - lines connecting the places */
function drawEdges() {
edges.forEach((edge)=>{
ctx.beginPath();
ctx.strokeStyle = "grey";
ctx.moveTo(edge.node1.x, edge.node1.y);
ctx.lineTo(edge.node2.x, edge.node2.y);
ctx.stroke();
});
}
/* Draw the distance box on top of the edge */
function drawDistances() {
edges.forEach((edge)=>{
let cx = (( edge.node1.x + edge.node2.x ) / 2) - 15;
let cy = (( edge.node1.y + edge.node2.y ) / 2) - 7;
ctx.fillStyle = "blue";
ctx.fillRect(cx, cy, 30, 15);
ctx.font = "12px Arial";
ctx.fillStyle = "white";
ctx.fillText(`${Math.floor(edge.distance)}`, cx+5, cy+11);
});
}
</script>
</body>
</html>
Solution
C[v] is more specifically the cheapest incoming edge whose other endpoint does not belong to Q. The initialization should be
place.C = Infinity;
place.E = null;
- Is it possible to pull css values with HTA javascript?
- What a strange syntax?
- JavaScript / Jest: How to show logs from test case only when test fails?
- How to secure my login page
- How can I create a two-way mapping in JavaScript, or some other way to swap out values?
- Route "/[locale]" used `params.locale`. `params` should be awaited before using its properties
- Page.locator() is the recommended way to select and interact with elements. Why does it offer less functionalities than Page.$()?
- How to filter object array based on attributes?
- How do you convert from emoji to unicode escapes in JS
- How to simulate a mouse click?
- Is it possible to add a single item to a vis.js timeline?
- How to ensure order of Cypress request execution
- Jquery Ajax Problem
- Can I run a function after navigating to a new page and waiting for that page to finish loading?
- Cannot start cocos after adding a new file
- Active link with React-Router?
- Is there a way to schedule offline notifications in a pwa?
- How to get the grid coordinates of an element using JavaScript?
- Bootstrap popper.js Failed to find a valid digest in the 'integrity' attribute for resource
- LeafLet map doesnt render properly on modal
- Create object from array
- How to ignore lines of code from coverage in vitest?
- How to manage CORS in Django
- How can I get an element's Accessible Name in javascript in the browser?
- TypeError: fs.readFileSync is not a function in Next.js
- Show hide divs on click in HTML and CSS without jQuery
- If an IIFE contains just one variable declaration that is immediately exported to global scope, why bother with it?
- Need explanation on following type of Javascript code
- What does an array literal with the `for` keyword inside mean in JavaScript?
- How to call a function every minute in a React component?