SHARE
TWEET

Untitled

a guest May 25th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const Queue = require("./Queue");
  2. const Stack = require("./Stack");
  3. const PriorityQueue = require("./PriorityQueue");
  4.  
  5. class Graph {
  6.    constructor() {
  7.       this.edges = {};
  8.       this.nodes = [];
  9.    }
  10.  
  11.    addNode(node) {
  12.       this.nodes.push(node);
  13.       this.edges[node] = [];
  14.    }
  15.  
  16.    addEdge(node1, node2, weight = 1) {
  17.       this.edges[node1].push({ node: node2, weight: weight });
  18.       this.edges[node2].push({ node: node1, weight: weight });
  19.    }
  20.  
  21.    addDirectedEdge(node1, node2, weight = 1) {
  22.       this.edges[node1].push({ node: node2, weight: weight });
  23.    }
  24.  
  25.    // addEdge(node1, node2) {
  26.       //   this.edges[node1].push(node2);
  27.       //   this.edges[node2].push(node1);
  28.    // }
  29.  
  30.    // addDirectedEdge(node1, node2) {
  31.       //   this.edges[node1].push(node2);
  32.    // }
  33.  
  34.    display() {
  35.       let graph = "";
  36.       this.nodes.forEach(node => {
  37.          graph += node + "->" + this.edges[node].map(n => n.node).join(", ") + "\n";
  38.       });
  39.       console.log(graph);
  40.    }
  41.  
  42.    djikstraAlgorithm(startNode) {
  43.       let distances = {};
  44.  
  45.       // Stores the reference to previous nodes
  46.       let prev = {};
  47.       let pq = new PriorityQueue(this.nodes.length * this.nodes.length);
  48.  
  49.       // Set distances to all nodes to be infinite except startNode
  50.       distances[startNode] = 0;
  51.       pq.enqueue(startNode, 0);
  52.  
  53.       this.nodes.forEach(node => {
  54.          if (node !== startNode) distances[node] = Infinity;
  55.          prev[node] = null;
  56.       });
  57.  
  58.       while (!pq.isEmpty()) {
  59.          let minNode = pq.dequeue();
  60.          let currNode = minNode.data;
  61.          let weight = minNode.priority;
  62.  
  63.          this.edges[currNode].forEach(neighbor => {
  64.             let alt = distances[currNode] + neighbor.weight;
  65.             if (alt < distances[neighbor.node]) {
  66.                distances[neighbor.node] = alt;
  67.                prev[neighbor.node] = currNode;
  68.                pq.enqueue(neighbor.node, distances[neighbor.node]);
  69.             }
  70.          });
  71.       }
  72.       return distances;
  73.    }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top