Dijkstra Binary Heap PQ
Tags: hacktoberfest
Published: 2020-10-30 13:53:46

    
Last program of Java Script


        class weightedGraph {
            constructor() {
                this.adjacencyList = {};
            }
            addVertex(vertex) {
                if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
                console.log(` ->   ${vertex}`)
            }

            addEdge(vertex1,vertex2, weight) {
                this.adjacencyList[vertex1].push({node: vertex2, weight});
                this.adjacencyList[vertex2].push({node :vertex1, weight});
                console.log(` ->   graph.addEdge ("${vertex1}", "${vertex2}", ${weight})`)
            }

            Dijkstra(start, finish) {
                const nodes = new PriorityQueue();
                const distances = {};
                const previous = {};
                let path = [] // to return at end
                let smallest

                // 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) {
                        // WE ARE DONE 
                        // BUILD UP PATH TO RETURN AT END 
                        while(previous[smallest]) {
                            path.push(smallest);
                            smallest = previous[smallest];
                        }
                        break;
                    }
                    if(smallest || distances[smallest] !== Infinity) {
                        for(let neighbor in this.adjacencyList[smallest]) {
                            // find neighboring node
                            let nextNode = this.adjacencyList[smallest][neighbor]; 
                            // Calculate new distances to neighboring node
                            let candidate = distances[smallest] + nextNode.weight;
                            let nextNeighbor = nextNode.node
                            if(candidate < distances[nextNeighbor]) {
                                // Upadating new smallest distance to neighbor 
                                distances[nextNeighbor] = candidate; 
                                // Upadating previous - How we got to neighbor
                                previous[nextNeighbor] = smallest;
                                // enqueue in priority queue with new priority
                                nodes.enqueue(nextNeighbor, candidate);
                            }
                        }
                    }
                 }
                 console.log(path.concat(smallest).reverse());
            }
        }

        class priorityQueue {
            constructor() {
                this.values = []
            }
            enqueue(val, priority) {
                let newNode = new Node(val, priority)
                this.values.push(newNode);
                this.bubbleUp();
            }

            bubbleUp() {
                let idx = this.values.length - 1;
                const element = this.values[idx];
                while(idx > 0) {
                    let parentIdx = Math.floor((idx - 1)/2);
                    let parent = this.values[parentIdx];
                    if(element.priority <= parent.priority) break;
                    this.values[parentIdx] = element;
                    this.values[idx] = parent;
                    idx = parentIdx;
                }
            }

            dequeue () {
              const min = this.values[0];
              const end = this.values.pop();
                  if(this.values.length > 0) {
                  this.values[0] = end;
                  this.sinkDown()
              }
              return min;
            }
            sinkDown() {
                let idx = 0;
                const length = this.values.length;
                const element = this.values[0];
                while(true) {
                    let leftChildIdx = 2 * idx + 1;
                    let rightChildIdx = 2 * idx + 2;
                    let leftChild,rightChild;
                    let swap = null;
                    if(leftChildIdx < length) {
                        leftChild = this.values[leftChildIdx];
                        if(leftChild.priority < element.priority) {
                            swap = leftChildIdx; 
                        }
                    }
                    if(rightChildIdx < length) {
                        rightChild = this.values[rightChildIdx];
                        if(
                            (swap === null && rightChild.priority < element.priority) 
                                                   ||
                            (swap !== null && rightChild.priority < leftChild.priority)
                         ) {
                            swap = rightChildIdx;
                        } 
                    }

                    if(swap === null) break;
                    this.values[idx] = this.values[swap]
                    this.values[swap] = element;
                }
            }
        }

        class Node {
            constructor(val, priority) {
                this.val = val;
                this.priority = priority;
            }
        }

        var graph = new weightedGraph();
        console.log("<---value--->")
        graph.addVertex("A")
        graph.addVertex("B")
        graph.addVertex("C")
        graph.addVertex("D")
        graph.addVertex("E")
        graph.addVertex("F")
        console.log("<---AddEdg value--->") 
        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);
        console.log("<---Dijkstra's value--->")
        graph.Dijkstra("A", "E");