dijkstra.js

const PriorityQueue = require("./minBinaryHeapPriority");

class WeightedGraph {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }
  addEdge(vertexOne, vertexTwo, weight) {
    if (this.adjacencyList[vertexOne] && this.adjacencyList[vertexTwo]) {
      this.adjacencyList[vertexOne].push({ node: vertexTwo, weight });
      this.adjacencyList[vertexTwo].push({ node: vertexOne, weight });
    }
  }
  dijkstra(start, finish) {
    const priorityQueue = new PriorityQueue();
    const distances = {};
    const previousNodes = {};
    const path = [];
    let smallest;

    for (const node in this.adjacencyList) {
      if (node === start) {
        priorityQueue.enqueue(start, 0);
        distances[node] = 0;
      } else {
        distances[node] = Infinity;
      }
      previousNodes[node] = null;
    }
    while (priorityQueue.values.length) {
      smallest = priorityQueue.dequeue().value;
      if (smallest === finish) {
        while (smallest) {
          path.push(smallest);
          smallest = previousNodes[smallest];
        }

        break;
      }
      if (smallest) {
        for (const neighbour of this.adjacencyList[smallest]) {
          const newDistance = neighbour.weight + distances[smallest];
          if (newDistance < distances[neighbour.node]) {
            distances[neighbour.node] = newDistance;
            priorityQueue.enqueue(neighbour.node, newDistance);
            previousNodes[neighbour.node] = smallest;
          }
        }
      }
    }
    return path.reverse();
  }
}

var graph = new WeightedGraph();
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(shortestPath);

minBinaryHeapPriority.js

class Node {
  constructor(value, priority) {
    this.value = value;
    this.priority = priority;
  }
}

class MinBinaryHeap {
  constructor() {
    this.values = [];
  }
  enqueue(value, priority) {
    const node = new Node(value, priority);
    this.values.push(node);
    this.bubbleUp();
  }
  bubbleUp() {
    let indx = this.values.length - 1;
    const element = this.values[indx];
    while (indx > 0) {
      const parentIndx = Math.floor((indx - 1) / 2);
      const parent = this.values[parentIndx];
      if (parent.priority <= element.priority) break;
      this.values[parentIndx] = element;
      this.values[indx] = parent;
      indx = parentIndx;
    }
  }
  dequeue() {
    const first = this.values.shift();
    const length = this.values.length;
    if (length > 0) {
      this.values.unshift(this.values.pop());
      this.sinkDown();
    }
    return first;
  }
  sinkDown() {
    let indx = 0;
    let element = this.values[0];
    const length = this.values.length;
    while (true) {
      let leftIndx = indx * 2 + 1;
      let rightIndx = indx * 2 + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftIndx < length) {
        leftChild = this.values[leftIndx];
        if (leftChild.priority < element.priority) {
          swap = leftIndx;
        }
      }
      if (rightIndx < length) {
        rightChild = this.values[rightIndx];
        if (
          (rightChild.priority < element.priority && swap === null) ||
          (swap !== null && rightChild.priority < leftChild.priority)
        ) {
          swap = rightIndx;
        }
      }

      if (swap === null) break;
      this.values[indx] = this.values[swap];
      this.values[swap] = element;

      indx = swap;
    }
  }
}

module.exports = MinBinaryHeap;