| class Node { | |
| constructor(val,priority) { | |
| this.val = val; | |
| this.priority = priority; | |
| } | |
| } | |
| class PriorityQueue { | |
| constructor() { | |
| this.values = []; | |
| } | |
| dequeue() { | |
| let oldMax = this.values[0]; | |
| let newMax = this.values.pop(); | |
| if(this.values.length > 0) { | |
| this.values[0] = newMax; | |
| this.bubbleDown() | |
| } | |
| return oldMax | |
| } | |
| enqueue(val,priority) { | |
| let newNode = new Node(val,priority) | |
| this.values.push(newNode); | |
| this.bubbleUp(); | |
| return this; | |
| } | |
| bubbleUp() { | |
| let index = this.values.length - 1; | |
| let parentIndex = Math.floor((index - 1) / 2); | |
| while(this.values[parentIndex] && this.values[parentIndex]['priority'] > this.values[index]['priority']){ | |
| let temp = this.values[index]; | |
| this.values[index]= this.values[parentIndex]; | |
| this.values[parentIndex] = temp; | |
| index = parentIndex; | |
| parentIndex = Math.floor((index - 1) / 2); | |
| } | |
| } | |
| bubbleDown() { | |
| let index = 0; | |
| let leftChildIndex,rightChildIndex; | |
| while(true) { | |
| leftChildIndex = (2 * index) + 1; | |
| rightChildIndex = (2 * index) + 2; | |
| let swappedIndex = null; | |
| if(leftChildIndex < this.values.length) { | |
| if(this.values[leftChildIndex]['priority'] < this.values[index]['priority']) { | |
| swappedIndex = leftChildIndex | |
| } | |
| } | |
| if(rightChildIndex < this.values.length) { | |
| if(swappedIndex && this.values[rightChildIndex]['priority'] < this.values[swappedIndex]['priority']){ | |
| swappedIndex = rightChildIndex; | |
| } else if(!swappedIndex && this.values[rightChildIndex]['priority'] < this.values[index]['priority']) { | |
| swappedIndex = rightChildIndex; | |
| } | |
| } | |
| if(swappedIndex) { | |
| let temp = this.values[index]; | |
| this.values[index] = this.values[swappedIndex]; | |
| this.values[swappedIndex] = temp; | |
| index = swappedIndex; | |
| } else { | |
| break; | |
| } | |
| } | |
| } | |
| } | |
| class WeightedGraph { | |
| constructor() { | |
| this.adjacencyList = {} | |
| } | |
| addVertex(v) { | |
| if(!this.adjacencyList[v]) { | |
| this.adjacencyList[v] = []; | |
| } | |
| } | |
| addEdge(vertex1,vertex2,weight) { | |
| this.adjacencyList[vertex1].push({ | |
| node: vertex2, | |
| weight : weight | |
| }) | |
| this.adjacencyList[vertex2].push({ | |
| node: vertex1, | |
| weight : weight | |
| }) | |
| } | |
| Dijkstra(start,finish){ | |
| const nodes = new PriorityQueue(); | |
| const distances = {}; | |
| const previous = {}; | |
| let smallest; | |
| let path = [] // to return at end | |
| //build up initial state | |
| for(let vertex in this.adjacencyList){ | |
| if(vertex === start) { | |
| distances[vertex] = 0; | |
| nodes.enqueue(vertex,0) | |
| } else { | |
| distances[vertex] = Infinity; | |
| nodes.enqueue(vertex,Infinity); | |
| } | |
| previous[vertex] = null; | |
| } | |
| // as long as there is something to visit | |
| while(nodes.values.length) { | |
| smallest = nodes.dequeue().val; | |
| if(smallest === finish) { | |
| //done | |
| //console.log(distances) | |
| //console.log(previous) | |
| while(previous[smallest]) { | |
| path.push(smallest); | |
| smallest =previous[smallest]; | |
| } | |
| break; | |
| // build path to return | |
| } | |
| if(smallest || distances[smallest] !== Infinity) { | |
| for(let neighour in this.adjacencyList[smallest]){ | |
| //find neighouring nodes | |
| let nextNode = this.adjacencyList[smallest][neighour]; | |
| //calculate new distance to neighouring node | |
| let candidate = distances[smallest] + nextNode.weight; | |
| let nexNeighbour = nextNode.node; | |
| if(candidate < distances[nexNeighbour]) { | |
| // updating new smallest distanceto neighour | |
| distances[nexNeighbour] = candidate; | |
| // updating previous - How we got to neighour | |
| previous[nexNeighbour] = smallest; | |
| //enqueue in priority queue with new priority | |
| nodes.enqueue(nexNeighbour,candidate); | |
| } | |
| } | |
| } | |
| } | |
| return path.concat(smallest).reverse(); | |
| } | |
| } | |
| var graph = new WeightedGraph(); | |
| graph.addVertex("A"); | |
| graph.addVertex("B"); | |
| graph.addVertex("C"); | |
| graph.addVertex("D"); | |
| graph.addVertex("E"); | |
| graph.addVertex("F"); | |
| graph.addEdge("A","B",4); | |
| graph.addEdge("A","C",2); | |
| graph.addEdge("B","E",3); | |
| graph.addEdge("C","D",2); | |
| graph.addEdge("C","F",4); | |
| graph.addEdge("D","E",3); | |
| graph.addEdge("D","F",1); | |
| graph.addEdge("E","F",1); | |