🍪.md

<title>Shortest Path Visualization</title> <style> canvas { border: 1px solid #000000; } </style>

Shortest Path Visualization

<script> // Vertex class to represent each HTML element class Vertex { constructor(id, x, y) { this.id = id; // id of the vertex this.x = x; // x-coordinate of the vertex this.y = y; // y-coordinate of the vertex this.adjacent = []; // array to store adjacent vertices } // Function to add an adjacent vertex addAdjacent(vertex) { this.adjacent.push(vertex); } } // Graph class to hold all the vertices class Graph { constructor() { this.vertices = []; // array to store all vertices this.map = {}; // hash map to store vertices by their ids } // Function to add a vertex to the graph addVertex(vertex) { this.vertices.push(vertex); this.map[vertex.id] = vertex; // add vertex to the map } } // Function to calculate the Euclidean distance between two vertices function getDistance(v1, v2) { const dx = v1.x - v2.x; const dy = v1.y - v2.y; return Math.sqrt(dx * dx + dy * dy); } // Function to draw the shortest path on the canvas function drawShortestPath(graph, path) { const canvas = document.getElementById("canvas2"); const ctx = canvas.getContext("2d"); ctx.clearRect(0, 0, canvas.width, canvas.height); // clear the canvas // Draw all vertices as white circles graph.vertices.forEach((vertex) => { ctx.beginPath(); ctx.arc(vertex.x, vertex.y, 10, 0, 2 * Math.PI); ctx.fillStyle = "#FFFFFF"; ctx.fill(); ctx.closePath(); }); // Draw the path as a red line ctx.beginPath(); ctx.strokeStyle = "#FF0000"; ctx.lineWidth = 3; for (let i = 0; i < path.length - 1; i++) { const current = path[i]; const next = path[i+1]; ctx.moveTo(current.x, current.y); ctx.lineTo(next.x, next.y); } ctx.stroke(); ctx.closePath(); } // Function to find the shortest path using the Held-Karp algorithm function tsp(graph) { const vertices = graph.vertices; const permutations = generatePermutations(vertices.slice(1)); // Generate all permutations except the starting vertex let shortestPath = null; let shortestDistance = Infinity; permutations.forEach((permutation) => { const path = [vertices[0], ...permutation]; // Add the starting vertex at the beginning of the permutation const distance = getPathDistance(path); if (distance < shortestDistance) { shortestPath = path; shortestDistance = distance; } }); return shortestPath; } // Function to generate all possible permutations of an array function generatePermutations(arr) { const permutations = []; function swap(i, j) { const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function permute(start) { if (start === arr.length - 1) { permutations.push([...arr]); return; } for (let i = start; i < arr.length; i++) { swap(start, i); permute(start + 1); swap(start, i); } } permute(0); return permutations; } // Function to calculate the total distance of a given path function getPathDistance(path) { let distance = 0; for (let i = 0; i < path.length - 1; i++) { distance += getDistance(path[i], path[i+1]); } return distance; } // Example usage const graph = new Graph(); const vertices = [ { id: "A", x: 150, y: 200 }, { id: "B", x: 90, y: 200 }, { id: "C", x: 95, y: 220 }, { id: "D", x: 165, y: 230 }, { id: "E", x: 316, y: 225 }, { id: "F", x: 100, y: 276 }, { id: "G", x: 235, y: 260 }, { id: "H", x: 265, y: 270 }, { id: "I", x: 360, y: 320 }, { id: "J", x: 370, y: 340 }, { id: "O", x: 330, y: 360 }, { id: "R", x: 310, y: 390 }, // { id: "T", x: 360, y: 385 }, // { id: "V", x: 360, y: 460 }, // { id: "W", x: 270, y: 480 }, // { id: "Z", x: 120, y: 530 }, // { id: "MissionTrails", x: 640, y: 50}, // { id: "Walmart", x: 500, y: 590}, // { id: "Costco", x: 670, y: 190} ]; function updateGraph() { // Define HTML elements and their positions dynamically // Clear the existing graph graph.vertices = []; graph.map = {}; // Add vertices to the graph vertices.forEach((vertex) => { const v = new Vertex(vertex.id, vertex.x, vertex.y); graph.addVertex(v); }); // Update adjacency relationships based on the current positions graph.vertices.forEach((vertex) => { const closestVertices = graph.vertices .filter((v) => v.id !== vertex.id) .sort((a, b) => getDistance(vertex, a) - getDistance(vertex, b)); closestVertices.forEach((v) => { vertex.addAdjacent(v); }); }); } // Update the graph initially updateGraph(); // Find the shortest path using the Held-Karp algorithm const shortestPath = tsp(graph); // Draw the shortest path on the canvas drawShortestPath(graph, shortestPath); // Store the pixel length in a global variable called path_length const path_length = Math.round(getPathDistance(shortestPath)); // Log the pixel length to the console console.log("Pixel length of shortest path:", path_length); </script>