const graph = {
    A: {B: 3, C: 4, D: 2},
    B: {A: 3, D: 6, E: 1},
    C: {A: 4, D: 1, F: 3},
    D: {A: 2, B: 6, C: 1, E: 5},
    E: {B: 1, D: 5, J: 1},
    F: {C: 3, G: 2, J: 5},
    G: {F: 2, H: 1, I: 3},
    H: {G: 1, I: 1, X: 2},
    I: {G: 3, H: 1, X: 8},
    J: {E: 1, F: 5, X: 6},
    X: {H: 2, I: 8, J: 6},
};

// The class Dsp:

class Dsp {
  constructor() {
    //Previous node after update of distance
    this.prev = {};
    //Distances of each node
    this.distances = {};
    //Array of unvisited neighbors
    this.unvisitedn = [];
    //Path of visited nodes from first to final node
    this.path = [];
  }

  findsp(graph, start, end) {

    //Register graph data 
    this.registerGraphData(graph, start);

    //Set the starting node as the current node
    let cn = start;

    //While there are unvisited nodes
    while (this.unvisitedn.length > 0) {
      //Mark the currentNode as visited
      this.markAsVisited(cn);

      //Compare distance from current node to unvisited neighbors
      let nodes = this.compareNodeDistances(graph, cn);

      //Update neighbor distance
      this.updateNodeDistances(nodes, cn);

      //Compare each unvisited neighbor and choose the one with the lowest distances
      //Set the choosed node as the new current node
      cn = this.selectNextNode(graph, cn);
    }

    return this.generatePath(start, end);
  }

  registerGraphData(graph, start) {

    //Set starting weight for all nodes
    const higherWeight = 10000;

    //For each node in the graph
    for (let node in graph) {
      //If the node is the starting node 
      if (node == start)
        //Set starting weight as 0
        this.distances[node] = 0;
      //else set the higherWeight
      else
        this.distances[node] = higherWeight;

      //Add to the unvisited nodes
      this.unvisitedn.push(node);
    }

    console.log(this.distances);
    console.log(this.unvisitedn);
  }

  markAsVisited(cn) {

    console.log('Visiting', cn);

    let index = this.unvisitedn.indexOf(cn);
    this.unvisitedn.splice(index, 1);
  }

  getUnvisitedNeighbors(graph, cn) {

    //All current node neighbors
    let nbs = graph[cn];
    let unbs = [];

    for (let nb in nbs) {
      if (this.unvisitedn.includes(nb))
        unbs.push(nb);
    }

    console.log(cn, 'Unvisited neighbors:', unbs);

    return unbs;
  }

  compareNodeDistances(graph, cn) {

    let unbs = this.getUnvisitedNeighbors(graph, cn);

    //new distances
    let newDistances = {};

    //For all currentNode neighbors
    for (let nb of unbs) { //Substituted unbs

      //Neighbor Weight
      let nbw = graph[cn][nb];
      //console.log('Neighbor weight', nbw);

      //neighbor distance
      let nbd = this.distances[nb];
      //console.log('Neighbor distance', nbd);

      //current node distance
      let cnd = this.distances[cn];
      //console.log('Current node distance', cnd);

      //If the neighbor distance > current node distance + neighbor weight
      if (nbd > cnd + nbw)
        newDistances[nb] = cnd + nbw;
    }

    console.log('new distances:', newDistances);

    return newDistances;
  }

  updateNodeDistances(nodes, cn) {

    //Update distances for each neighbor that was compared
    for (let node in nodes) {
      console.log(nodes);


      this.distances[node] = nodes[node];
      this.prev[node] = cn;
    }

    console.log("Node distances after update", this.distances);
    console.log("Node previous nodes after update", this.prev);
  }

  selectNextNode(graph, cn) {
    let unbs = this.getUnvisitedNeighbors(graph, cn);
    let mind = 100000;
    let nextn = null;

    //If there are unvisited neighbors
    if (unbs.length > 0) {
      for (let nb of unbs) {
        if (this.distances[nb] < mind) {
          mind = this.distances[nb];
          nextn = nb;
        }
      }
    } else {
      nextn = this.unvisitedn[0];
    }

    return nextn;
  }

  generatePath(start, end) {

    let cn = end;
    let path = {};
    let nodes = [];

    while (cn !== start) {
      nodes.push(cn);
      cn = this.prev[cn];
    }

    nodes.push(start);
    nodes.reverse();

    path['nodes'] = nodes;
    path['distance'] = this.distances[end];

    return path;
  }
}

let shp = new Dsp();

console.log(shp.findsp(graph, 'A', 'I'));

/* MinHeap minimised - taken from https://stackoverflow.com/a/66511107/5459839 */
const MinHeap={siftDown(h,i=0,v=h[i]){if(i<h.length){let k=v[0];while(1){let j=i*2+1;if(j+1<h.length&&h[j][0]>h[j+1][0])j++;if(j>=h.length||k<=h[j][0])break;h[i]=h[j];i=j;}h[i]=v}},heapify(h){for(let i=h.length>>1;i--;)this.siftDown(h,i);return h},pop(h){return this.exchange(h,h.pop())},exchange(h,v){if(!h.length)return v;let w=h[0];this.siftDown(h,0,v);return w},push(h,v){let k=v[0],i=h.length,j;while((j=(i-1)>>1)>=0&&k<h[j][0]){h[i]=h[j];i=j}h[i]=v;return h}};

function DijkstraShortestPath(graph, start, end) {
    // Heap with one entry: distance is 0 at start, and there is no previous.
    let heap = [[0, start, null]]; 
    let prev = {};
    
    while (heap.length) {
        let [distance, current, cameFrom] = MinHeap.pop(heap);
        if (current in prev) continue; // Already visited
        prev[current] = cameFrom; // Mark as visited
        if (current == end) { // Found!
            // Reconstruct path
            let path = [];
            while (current) {
                path.push(current);
                current = prev[current];
            }
            path.reverse();
            return { path, distance };
        }
        // Push unvisited neighbors on the heap
        for (let [neighbor, edge] of Object.entries(graph[current])) {
            if (!(neighbor in prev)) MinHeap.push(heap, [distance + edge, neighbor, current]);
        }
    }
}

// Demo:
const graph = {
    A: {B: 3, C: 4, D: 2},
    B: {A: 3, D: 6, E: 1},
    C: {A: 4, D: 1, F: 3},
    D: {A: 2, B: 6, C: 1, E: 5},
    E: {B: 1, D: 5, J: 1},
    F: {C: 3, G: 2, J: 5},
    G: {F: 2, H: 1, I: 3},
    H: {G: 1, I: 1, X: 2},
    I: {G: 3, H: 1, X: 8},
    J: {E: 1, F: 5, X: 6},
    X: {H: 2, I: 8, J: 6},
}

console.log(DijkstraShortestPath(graph, 'A', 'I'));