Dijkstra First Version
Tags: hacktoberfest
Published: 2020-10-30 12:11:21

    class PriorityQueue {
      constructor(){
        this.values = [];
      }
      enqueue(val, priority) {
        this.values.push({val, priority});
        this.sort();
        return values
      };
      dequeue() {
        return this.values.shift();
      };
      sort() {
        this.values.sort((a, b) => a.priority - b.priority);
      };
    }

    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());
        }
    }

    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");