cloudTravel

cloudTravel.js

"use strict";

function PriorityQueue() {
  this.collection = [];
}

PriorityQueue.prototype.enqueue = function(element) {
  if (this.isEmpty()) {
    this.collection.push(element);
  } else {
    let added = false;
    for (let i = 1; i <= this.collection.length; i++) {
      if (element[1] < this.collection[i - 1][1]) {
        this.collection.splice(i - 1, 0, element);
        added = true;
        break;
      }
    }
    if (!added) {
      this.collection.push(element);
    }
  }
};

PriorityQueue.prototype.dequeue = function() {
  let value = this.collection.shift();
  return value;
};

PriorityQueue.prototype.isEmpty = function() {
  return this.collection.length === 0;
};

function ShortestTrip(latitudes, longitudes, canTravel, radius) {
  this.latitudes = latitudes;
  this.longitudes = longitudes;
  this.canTravel = canTravel;
  this.radius = radius;
  this.adjList = {};
  this.map = {};
  this.latitudes.forEach((_, index) => {
    this.map[index] = {
      minDist: index == 0 ? 0 : Infinity,
      previousIndex: ""
    };
  });
}

ShortestTrip.prototype.buildAdjList = function() {
  this.canTravel.forEach(travel => {
    let edge = travel.split(" ");
    if (!this.adjList[edge[0]]) {
      this.adjList[edge[0]] = { [edge[1]]: this.getWeight(edge[0], edge[1]) };
    } else {
      this.adjList[edge[0]][edge[1]] = this.getWeight(edge[0], edge[1]);
    }
  });
};

ShortestTrip.prototype.getWeight = function(start, end) {
  let lat1 = this.latitudes[start];
  let lon1 = this.longitudes[start];
  let lat2 = this.latitudes[end];
  let lon2 = this.latitudes[end];

  return (
    this.radius *
    Math.acos(
      Math.sin(lat1) * Math.sin(lat2) +
        Math.cos(lat1) * Math.cos(lat2) * Math.cos(lon1 - lon2)
    )
  );
};

ShortestTrip.prototype.findPathWithDijkstra = function(startNode) {
  let pq = new PriorityQueue();
  pq.enqueue([startNode, 0]);

  while (!pq.isEmpty()) {
    let shortestStep = pq.dequeue();
    let currentNode = shortestStep[0];

    if (!this.adjList[currentNode]) return;
    Object.keys(this.adjList[currentNode]).forEach(neighbor => {
      let time =
        this.map[currentNode].minDist + this.adjList[currentNode][neighbor];
      if (time < this.map[neighbor].minDist) {
        this.map[neighbor].minDist = time;
        this.map[neighbor].previousIndex = currentNode;
        pq.enqueue([neighbor, time]);
      }
    });
  }
};

let latitudes = [0, 0, 70, 50, 87];
let longitudes = [90, 0, 45, 35, 0];
let canTravel = ["1 2", "0 2", "0 1", "2 4", "2 3", "3 2"];
let start = 0;
let end = 4;
let radius = 4000;

let shortestPath = new ShortestTrip(latitudes, longitudes, canTravel, radius);

shortestPath.buildAdjList();

shortestPath.findPathWithDijkstra(0, 2);
console.log(shortestPath.map[end].minDist);