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");
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)