Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function djikstraAlgorithm(startNode) {
- let distances = {};
- // Stores the reference to previous nodes
- let prev = {};
- let pq = new PriorityQueue(this.nodes.length * this.nodes.length);
- // Set distances to all nodes to be infinite except startNode
- distances[startNode] = 0;
- pq.enqueue(startNode, 0);
- this.nodes.forEach(node => {
- if (node !== startNode) distances[node] = Infinity;
- prev[node] = null;
- });
- while (!pq.isEmpty()) {
- let minNode = pq.dequeue();
- let currNode = minNode.data;
- let weight = minNode.priority;
- this.edges[currNode].forEach(neighbor => {
- let alt = distances[currNode] + neighbor.weight;
- if (alt < distances[neighbor.node]) {
- distances[neighbor.node] = alt;
- prev[neighbor.node] = currNode;
- pq.enqueue(neighbor.node, distances[neighbor.node]);
- }
- });
- }
- return distances;
- }
- class Graph {
- constructor() {
- this.edges = {};
- this.nodes = [];
- }
- addNode(node) {
- this.nodes.push(node);
- this.edges[node] = [];
- }
- addEdge(node1, node2) {
- this.edges[node1].push(node2);
- this.edges[node2].push(node1);
- }
- addDirectedEdge(node1, node2) {
- this.edges[node1].push(node2);
- }
- display() {
- let graph = ""; this.nodes.forEach(node => {
- graph += node + "->" + this.edges[node].join(", ") + "\n";
- });
- console.log(graph);
- }
- }
- let g = new Graph();
- g.addNode("A");
- g.addNode("B");
- g.addNode("C");
- g.addNode("D");
- g.addNode("E");
- g.addNode("F");
- g.addNode("G");
- g.addDirectedEdge("A", "C", 100);
- g.addDirectedEdge("A", "B", 3);
- g.addDirectedEdge("A", "D", 4);
- g.addDirectedEdge("D", "C", 3);
- g.addDirectedEdge("D", "E", 8);
- g.addDirectedEdge("E", "F", 10);
- g.addDirectedEdge("B", "G", 9);
- g.addDirectedEdge("E", "G", 50);
- var test = g.djikstraAlgorithm("A");
- console.log(test);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement