How to show the nodes with shortest distance from priority queue in dijkstra algorithm?

82 views Asked by At

let canvas = document.getElementById("graphCanvas");
                let ctx = canvas.getContext("2d");
                let outputDiv = document.getElementById("output");

                let nodes = {
                    A: { x: 128, y: 255, connections: ["B", "C", "F"] },
                    B: { x: 212, y: 85, connections: ["A", "C", "E"] },
                    C: { x: 42, y: 127, connections: ["A", "B", "F"] },
                    D: { x: 212, y: 382, connections: ["A", "E", "F"] },
                    E: { x: 340, y: 255, connections: ["B", "D"] },
                    F: { x: 42, y: 382, connections: ["A", "C", "D"] },
                };

                let edges = [
                    { from: "A", to: "B" },
                    { from: "A", to: "C" },
                    { from: "A", to: "D" },
                    { from: "A", to: "F" },
                    { from: "B", to: "C" },
                    { from: "B", to: "D" },
                    { from: "B", to: "E" },
                    { from: "C", to: "F" },
                    { from: "D", to: "E" },
                    { from: "D", to: "F" },
                ];

                edges.forEach((edge) => {
                    edge.weight = Math.floor(Math.random() * 14 + 1);
                });

                edges.forEach((edge) => {
                    ctx.beginPath();
                    ctx.moveTo(nodes[edge.from].x, nodes[edge.from].y);
                    ctx.lineTo(nodes[edge.to].x, nodes[edge.to].y);
                    ctx.stroke();
                    let midX = (nodes[edge.from].x + nodes[edge.to].x) / 2;
                    let midY = (nodes[edge.from].y + nodes[edge.to].y) / 2;
                    ctx.font = "20px Arial";
                    ctx.fillText(edge.weight, midX, midY);
                });

                for (let node in nodes) {
                    ctx.beginPath();
                    ctx.arc(nodes[node].x, nodes[node].y, 20, 0, 2 * Math.PI);
                    ctx.fillStyle = "white";
                    ctx.fill();
                    ctx.strokeStyle = "black";
                    ctx.stroke();
                    ctx.fillStyle = "black";
                    ctx.font = "20px Arial";
                    ctx.fillText(node, nodes[node].x - 10, nodes[node].y + 7);
                }
                class PriorityQueue {
                    constructor() {
                        this.queue = [];
                    }

                    enqueue(element, priority) {

                        this.queue.push({ element, priority });
                        this.sort();
                    }

                    dequeue() {

                        if (this.isEmpty()) {
                            return;
                        }
                        return this.queue.shift().element;
                    }

                    isEmpty() {
                        return this.queue.length === 0;
                    }

                    sort() {
                        this.queue.sort((a, b) => a.priority - b.priority);
                    }

                    printQueue() {

                        this.queue.forEach((item) => {
                            console.log(item.element);
                        });
                    }
                    getDistancesFromNode(node) {

                        let nodeObject = this.queue.find((item) => item.node === node);

                        return nodeObject ? nodeObject.distance : null;
                    }
                }

                function dijkstra(start) {
                    const distances = {};
                    const prev = {};
                    const priorityQueue = new PriorityQueue();

                    Object.keys(nodes).forEach((node) => {

                        distances[node] = Infinity;
                        prev[node] = null;
                    });

                    distances[start] = 0;
                    priorityQueue.enqueue(start, 0);


                    while (!priorityQueue.isEmpty()) {

                        let current = priorityQueue.dequeue();


                        edges
                            .filter((edge) => edge.from === current || edge.to === current)
                            .forEach((edge) => {
                                let otherNode = edge.from === current ? edge.to : edge.from;
                                let weight = edge.weight;

                                if (distances[current] + weight < distances[otherNode]) {

                                    distances[otherNode] = distances[current] + weight;
                                    prev[otherNode] = current;
                                    priorityQueue.enqueue(otherNode, distances[otherNode]);
                                }
                            });
                    }
                    return { distances, prev };
                }
                function validateInput() {
                    let result = dijkstra("A");
                    let correctDistances = result.distances;
                    let userAnswers = { A: 0 };

                    // Iterate through each node from A to F
                    for (let i = 1; i < 6; i++) {
                        let node = String.fromCharCode(65 + i); // 65 = A in ASCII code
                        let userInput;
                        do {
                            userInput = prompt(
                                "Please enter the shortest distance to the junction" +
                                node +
                                " in:"
                            );

                            if (correctDistances[node] == userInput) {
                                userAnswers[node] = userInput;
                                alert(
                                    "Correctly! The shortest distance to the junction" +
                                    node +
                                    " is " +
                                    userInput +
                                    "."
                                );
                                document.getElementById("distanceTo" + node).value = userInput;
                                break;
                            } else {
                                alert(
                                    "Wrong Input for node " +
                                    node +
                                    ". please try again"
                                );
                            }
                            if (userInput === null) {
                                break;
                            }
                        } while (true);
                    }
                }
                
document.addEventListener("DOMContentLoaded", function () {
  let resetButton = document.getElementById("reset");
  resetButton.addEventListener("click", function () {
location.reload();
  });
});
body {
  margin: 0;
  justify-content: start;
}

#mainContainer {
  display: flex;
  justify-content: start;
  align-items: start;
  resize: both;
  overflow: auto;
}

#graphCanvas {
  border: 1px solid black;
  width: 680px;
  height: 444px;

  overflow: auto;
}

#distanceTable,
#distanceTable th,
#distanceTable td {
  position: static;
  margin-bottom: 5px;
  border: 1px solid black;
  border-collapse: collapse;
  padding: 3px;
}
input[placeholder="node"] {
  width: 55px;
}
input[placeholder="Distance"] {
  width: 55px;
}

input[placeholder="Priority Queue"] {
  width: 240px;
}
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Shortest path Dijkstra algorithm by Ramo</title>
    <script defer src="dijkstra.js"></script>
    <link rel="stylesheet" href="style.css">
</head>


    <div id="mainContainer">
        <canvas id="graphCanvas" width="680" height="490"></canvas>
        <table id="distanceTable">
            <tr>
                <th>Knoten</th>
                <th>Kosten</th>
                <th>Priority Queue</th>
            </tr>
            <tr>
                <td>A</td>
                <td>0</td>
                <td>
                    <input type="text" id="priorityQueueA" placeholder="Priority QueueA">
                </td>

                </td>

            </tr>
            <tr>
                <td><input type="text" id="Element1" placeholder="node"></td>
                <td>
                    <input type="text" id="distanceToB" placeholder="Distance">
                </td>

                <td>
                    <input type="text" id="priorityQueueB" placeholder="Priority QueueB">
                </td>
            </tr>

            <tr>
                <td><input type="text" id="Element2" placeholder="node"></td>
                <td>
                    <input type="text" id="distanceToC" placeholder="Distance">
                </td>
                <td>
                    <input type="text" id="priorityQueueC" placeholder="Priority QueueC">
                </td>
            </tr>

            <tr>
            <tr>
                <td><input type="text" id="Element3" placeholder="node"></td>
                <td>
                    <input type="text" id="distanceToD" placeholder="Distance">
                </td>
                <td>
                    <input type="text" id="priorityQueueD" placeholder="Priority QueueD">
                </td>
            </tr>
            <tr>
                <td><input type="text" id="Element4" placeholder="node"></td>
                <td>
                    <input type="text" id="distanceToE" placeholder="Distance">
                </td>
                <td>
                    <input type="text" id="priorityQueueE" placeholder="Priority QueueE">
                </td>
            </tr>
            <tr>
                <td><input type="text" id="" placeholder="node"></td>
                <td>
                    <input type="text" id="distanceToF" placeholder="Distance">
                </td>
                <td>
                    <input type="text" id="priorityQueueF" placeholder="Priority QueueF">
                </td>

            </tr>

            <td><button id="reset">Reset</button></td>
            <td> <button id="verify" onclick=validateInput()>Verify</button></td>
            <td> <button id="verify" onclick=validateInputPq()>Verify</button></td>
        </table>
    </div>

Edit: I have now rewritten the code as an executable html file. My goal is to have the priority queue entered and verified by the user in the form (B12, C14, D15) etc. and that then the 1 element of the PQ (i.e. in the example B12) of the nodes is displayed and the user has to enter the shortest distance to and is verified and then the PQ of this node (i.e. B) until all nodes including the shortest distance to A are through!

0

There are 0 answers