javascripthtmlalgorithmminimum-spanning-treeprims-algorithm

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.. enter image description here

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;