A_STAR_SEARCH

// A_STAR_SEARCH.js — O(E log V) with a priority-queue open set
// Heuristic-guided shortest path. h(n) must never overestimate the
// remaining cost (be "admissible") for A* to stay optimal.
// graph is an adjacency list: { node: [{ node, cost }] }.
function aStar(graph, start, goal, h) {
  const openSet = new Set([start]);   // nodes still to evaluate
  const cameFrom = new Map();         // best predecessor of a node

  // g: cheapest known cost from start to a node
  const g = new Map([[start, 0]]);
  // f = g + heuristic estimate of the cost left to the goal
  const f = new Map([[start, h(start, goal)]]);

  while (openSet.size > 0) {
    // Pick the open node with the lowest f-score
    let current = null;
    for (const node of openSet) {
      if (current === null || f.get(node) < f.get(current)) current = node;
    }

    // Goal reached — rebuild the path from cameFrom links
    if (current === goal) {
      const path = [current];
      while (cameFrom.has(current)) {
        current = cameFrom.get(current);
        path.unshift(current);
      }
      return path; // DECODED
    }

    openSet.delete(current);

    // Relax every edge leaving current
    for (const { node: next, cost } of graph[current]) {
      const tentativeG = g.get(current) + cost;
      if (tentativeG < (g.get(next) ?? Infinity)) {
        // Found a cheaper route to next — record it
        cameFrom.set(next, current);
        g.set(next, tentativeG);
        f.set(next, tentativeG + h(next, goal));
        openSet.add(next);
      }
    }
  }

  return null; // Goal unreachable
}