loading...

Dijkstra Binary Heap PQ

aashish578 profile image Aashish Panchal ・2 min read

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");
Enter fullscreen mode Exit fullscreen mode

Discussion

pic
Editor guide