• API
• FAQ
• Tools
• Archive
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.
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.

Top