Dijkstra

const { MinPriorityQueue } = require("@datastructures-js/priority-queue");

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(vertex1, vertex2, weight) {
    this.adjacencyList[vertex1].push({ node: vertex2, weight });
    this.adjacencyList[vertex2].push({ node: vertex1, weight });
  }

  dijkstra(start, finish) {
    const nodes = new MinPriorityQueue({ priority: (x) => x.priority });
    const distances = {};
    const previous = {};
    let path = []; // to return at the end
    let smallest;

    // Build initial state
    for (let vertex in this.adjacencyList) {
      if (vertex === start) {
        distances[vertex] = 0;
        nodes.enqueue({ vertex, priority: 0 });
      } else {
        distances[vertex] = Infinity;
        nodes.enqueue({ vertex, priority: Infinity });
      }
      previous[vertex] = null;
    }

    // As long as there is something to visit
    while (!nodes.isEmpty()) {
      smallest = nodes.dequeue().element.vertex;
      if (smallest === finish) {
        // We are done
        // Build path to return at end
        while (previous[smallest]) {
          path.push(smallest);
          smallest = previous[smallest];
        }
        break;
      }

      if (smallest || distances[smallest] !== Infinity) {
        for (let neighbor in this.adjacencyList[smallest]) {
          // Find neighboring node
          let nextNode = this.adjacencyList[smallest][neighbor];
          // Calculate new distance to neighboring node
          let candidate = distances[smallest] + nextNode.weight;
          let nextNeighbor = nextNode.node;
          if (candidate < distances[nextNeighbor]) {
            // Updating new smallest distance to neighbor
            distances[nextNeighbor] = candidate;
            // Updating previous - How we got to neighbor
            previous[nextNeighbor] = smallest;
            // Enqueue in priority queue with new priority
            nodes.enqueue({ vertex: nextNeighbor, priority: candidate });
          }
        }
      }
    }

    // Return the shortest path and its distance
    return path.concat(smallest).reverse();
  }
}

// Example usage
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");

graph.addEdge("A", "B", 4);
graph.addEdge("A", "C", 2);
graph.addEdge("B", "E", 3);
graph.addEdge("C", "D", 2);
graph.addEdge("C", "F", 4);
graph.addEdge("D", "E", 3);
graph.addEdge("D", "F", 1);
graph.addEdge("E", "F", 1);

const shortestPath = graph.dijkstra("A", "E");
console.log("Shortest path:", shortestPath);