karimshalapy · December 4, 2020 16:06 · karimshalapy · Dec 4, 2020
diff --git a/Dijkstra'sAlgorithm.js b/Dijkstra'sAlgorithm.js
 //Dijkstra's algorithm uses a weighted graph (either directed or undirected) to get the shortest path between any two vertices
 //it's depenedant on creating a priority queue that we will push edges on it with the priority as the weight of the edge
 //here's a simple implementation of priority queue with enqueue and dequeue methods only
 //to read about priority queue check BinaryHeaps.js gist
 class QueueNode {
    constructor(val, priority) {
        this.val = val
        this.priority = priority
    }
 }
 class PriorityQueue {
    constructor() {
        this.values = []
    }
    swap(i1, i2) {
        const arr = this.values
        return [arr[i1], arr[i2]] = [arr[i2], arr[i1]]
    }
    calcParentIndex(childIndex) { return Math.floor((childIndex - 1) / 2) }
    calcChildrenIndices(parentIndex) {
        const x = 2 * parentIndex
        return [x + 1, x + 2]
    }
    enqueue(val, priority) {
        this.values.push(new QueueNode(val, priority))
        let valCurrentIndex = this.values.length - 1
        let parentIndex = this.calcParentIndex(valCurrentIndex)
        while (parentIndex >= 0 && this.values[parentIndex].priority > priority) {
            this.swap(valCurrentIndex, parentIndex)
            valCurrentIndex = parentIndex
            parentIndex = this.calcParentIndex(valCurrentIndex)
        }
        return this.values
    }
    dequeue() {
        if (this.values.length === 0) return null
        this.swap(0, this.values.length - 1)
        const poppedValue = this.values.pop()
        let sinkDownIdx = 0
        const { priority: sinkDownPriority } = this.values[sinkDownIdx] || { priority: Infinity }
        let [child1Idx, child2Idx] = this.calcChildrenIndices(sinkDownIdx)
        while ((child1Idx < this.values.length || child2Idx < this.values.length)) {

            const child1 = this.values[child1Idx]
            const child2 = this.values[child2Idx] || { priority: Infinity }
            if (child1.priority <= child2.priority && child1.priority < sinkDownPriority) {
                this.swap(child1Idx, sinkDownIdx)
                sinkDownIdx = child1Idx
            } else if (child2.priority < child1.priority && child2.priority < sinkDownPriority) {
                this.swap(child2Idx, sinkDownIdx)
                sinkDownIdx = child2Idx
            } else break
            [child1Idx, child2Idx] = this.calcChildrenIndices(sinkDownIdx)
        }
        return poppedValue
    }
 }
 //now we define Graph class as weighted graph
 //same logic as in Graph.js but instead of pushing the vertex onto the edges array, here we push an object that contains the node that edge corresponds to and the weight of that edge
 class Graph {
    constructor() {
        this.adjacencyList = {}
    }
    addOrRemove(v1, v2, weight, type) {
        const adjacencyList = this.adjacencyList
        if (adjacencyList.hasOwnProperty(v1) && adjacencyList.hasOwnProperty(v2)) {
            const v1Arr = adjacencyList[v1], v2Arr = adjacencyList[v2]
            const i1 = v1Arr.findIndex(item => item.node === v2)
            const i2 = v2Arr.findIndex(item => item.node === v1)
            if (i1 === -1 && i2 === -1 && type === "add") {
                v1Arr.push({ node: v2, weight })
                v2Arr.push({ node: v1, weight })
                return true
            } else if (i1 !== -1 && i2 !== -1 && type === "remove") {
                v1Arr.splice(i1, 1)
                v2Arr.splice(i2, 1)
                return true
            }
        }
        return false
    }
    addEdge(v1, v2, weight) { return this.addOrRemove(v1, v2, weight, "add") }
    addVertex(vertex) {
        if (this.adjacencyList[vertex]) throw new Error("Vertex already existing")
        this.adjacencyList[vertex] = []
        return this.adjacencyList[vertex]
    }
    //up to here it's all the same as logic explained before in other gists
    /////////////////////////////////////////////////////////////////////////////////////
    //a simple private method to create an object with the keys as all vertices and the value is passed down as an argument
    //the start argument should be the start vertex if we want to make sure that the start vertex has a different value than the rest
    createObjectFromVertices(newValue, start) {
        return Object.fromEntries(
            Object.entries(this.adjacencyList)
                .map(([key, value]) => { return [key, key === start ? 0 : newValue] })
        )
    }
    //it works as follows
    //we define an object or a hash map with all the vertices in the adjacency list of the current graph with the values set to null initially and as the logic continues null will represent the shortest path to it is going through which node
    //meaining, if we have {E: C} in the object, then that means the shortest path to E from whatever the start vertex is, is through the C vertex, and we can check the C vertex to see which way is shortest to it
    //doing that makes a map that gets the shortest way to any vertex from the startin vertex that's passed as an argument
    //so if we check the end vertex in this object and track the vertices shortest path until we reach the start, then this is the shortest path from the start vertex to the end
    //in order to that we'll need to have another object with all the vertices but the values here are set to Infinity this object will have the total distance from start to the key vertex
    //having this object will make us compare the length calculated at the current state with the one in the object and if the new calculated is shorter then we update both object accordingly
    //let's start
    dijkstra(start, end) {
        // we first start with the priority queue
        // by doing that the priority queue that is formed from a min binary heap will sort the smallest weight to the top
        // so when we pop the smallest item from the priority queue if it was the the destination vertex, then any other route would be longer so we stop looping and we get the shortest path
        const q = new PriorityQueue()
        //we create the object of distances with all vertices values set to Infinity except the start set to 0
        const distances = this.createObjectFromVertices(Infinity, start)
        //then we create the prev object that shows through chich previous node is the shortest path going like explained before
        const prev = this.createObjectFromVertices(null)
        //we start by enqueuing the start vertex and its distance, which is 0 (this is just the intitation step, the priority is not required here because it's the first and only item in the queue)
        q.enqueue(start, distances[start])
        //then we start a loop as long as there're items in the queue
        while (q.values.length) {
            //because that's a priority queue if we deuqueue an item then it's the smallest distance vecause it's a min binary heap
            //so we store the smallest value in a variable
            const smallest = q.dequeue().val
            //check smallest to see if it was the the same as the end vertex, 
            //if true then any other route would be longer so we stop looping and we get the shortest path, so we break 
            if (smallest === end) break
            //if it's not the end then we start looping over all the edges of the vertex
            this.adjacencyList[smallest].forEach(item => {
                //first we calculate the distance of the smallest vertex that was popped from the queue to the current vertex in the edges loop iteration
                //we do that by getting the shortest distance of the smallest that's stored in the the distances object, and we add that to the weight of the current edge that corresponds to both the vertices
                const currentItemDistanceFromStart = distances[smallest] + item.weight
                //compare the distance that's calculated to the one stored in distances object
                //(if this was the first time calculated, then it's getting compared to Infinity which is the initial value and obviously it will be the new minimum anyway, but if it was another calculation ti'll be compared to the previously stored distance)
                const currentItemMinDistanceFromStart = Math.min(distances[item.node], currentItemDistanceFromStart)
                //we check if the new minimum is smaller than the distance stored
                if (currentItemMinDistanceFromStart < distances[item.node]) {
                    //if it is smaller, then that's a new smaller distance from the current vertex to the start
                    //so we store it as the new value of distance for the current vertex in distances object
                    distances[item.node] = currentItemMinDistanceFromStart
                    //and we set the prev node that the shortest path is going through to be the current popped smallest item from the queue that we're looping over its edges right now
                    prev[item.node] = smallest
                    //and then we enqueue the current edge to the queue, with the weight as the shortest current distance from the start
                    q.enqueue(item.node, distances[item.node])
                    //by doing that after the first iteration of the while loop, we'll have the shortest path is through the start vertex for each nextdoor neighbor and the distances of each is the same as the weight of the edges
                    //but this is enquining into the queue so it will have the smallest distance ready, and ti'll scale and keep doing that untill we hit the end vertex
                }
                //if the newly calculated distance is not the smaller one, then we just skip doing anything and go to the next iteration in the while loop
            })
        }
        //this is a simple logic to tradc back the shortest path from the prev object from the start to the end vertex by check through which vertex is the path going through and push it in an array
        //keep iterating over untill we reach the start vertex and we break, so it will result in an array that has the order of vertices in which the shortest path is going through
        const ansArr = [end]
        let current = end
        while (current !== start) {
            const prevItem = prev[current]
            ansArr.push(prevItem)
            current = prevItem
        }
        //return the order of shortest path array
        return ansArr
    }
 }
	//Dijkstra's algorithm uses a weighted graph (either directed or undirected) to get the shortest path between any two vertices
	//it's depenedant on creating a priority queue that we will push edges on it with the priority as the weight of the edge
	//here's a simple implementation of priority queue with enqueue and dequeue methods only
	//to read about priority queue check BinaryHeaps.js gist
	class QueueNode {
	constructor(val, priority) {
	this.val = val
	this.priority = priority
	}
	}
	class PriorityQueue {
	constructor() {
	this.values = []
	}
	swap(i1, i2) {
	const arr = this.values
	return [arr[i1], arr[i2]] = [arr[i2], arr[i1]]
	}
	calcParentIndex(childIndex) { return Math.floor((childIndex - 1) / 2) }
	calcChildrenIndices(parentIndex) {
	const x = 2 * parentIndex
	return [x + 1, x + 2]
	}
	enqueue(val, priority) {
	this.values.push(new QueueNode(val, priority))
	let valCurrentIndex = this.values.length - 1
	let parentIndex = this.calcParentIndex(valCurrentIndex)
	while (parentIndex >= 0 && this.values[parentIndex].priority > priority) {
	this.swap(valCurrentIndex, parentIndex)
	valCurrentIndex = parentIndex
	parentIndex = this.calcParentIndex(valCurrentIndex)
	}
	return this.values
	}
	dequeue() {
	if (this.values.length === 0) return null
	this.swap(0, this.values.length - 1)
	const poppedValue = this.values.pop()
	let sinkDownIdx = 0
	const { priority: sinkDownPriority } = this.values[sinkDownIdx] \|\| { priority: Infinity }
	let [child1Idx, child2Idx] = this.calcChildrenIndices(sinkDownIdx)
	while ((child1Idx < this.values.length \|\| child2Idx < this.values.length)) {

	const child1 = this.values[child1Idx]
	const child2 = this.values[child2Idx] \|\| { priority: Infinity }
	if (child1.priority <= child2.priority && child1.priority < sinkDownPriority) {
	this.swap(child1Idx, sinkDownIdx)
	sinkDownIdx = child1Idx
	} else if (child2.priority < child1.priority && child2.priority < sinkDownPriority) {
	this.swap(child2Idx, sinkDownIdx)
	sinkDownIdx = child2Idx
	} else break
	[child1Idx, child2Idx] = this.calcChildrenIndices(sinkDownIdx)
	}
	return poppedValue
	}
	}
	//now we define Graph class as weighted graph
	//same logic as in Graph.js but instead of pushing the vertex onto the edges array, here we push an object that contains the node that edge corresponds to and the weight of that edge
	class Graph {
	constructor() {
	this.adjacencyList = {}
	}
	addOrRemove(v1, v2, weight, type) {
	const adjacencyList = this.adjacencyList
	if (adjacencyList.hasOwnProperty(v1) && adjacencyList.hasOwnProperty(v2)) {
	const v1Arr = adjacencyList[v1], v2Arr = adjacencyList[v2]
	const i1 = v1Arr.findIndex(item => item.node === v2)
	const i2 = v2Arr.findIndex(item => item.node === v1)
	if (i1 === -1 && i2 === -1 && type === "add") {
	v1Arr.push({ node: v2, weight })
	v2Arr.push({ node: v1, weight })
	return true
	} else if (i1 !== -1 && i2 !== -1 && type === "remove") {
	v1Arr.splice(i1, 1)
	v2Arr.splice(i2, 1)
	return true
	}
	}
	return false
	}
	addEdge(v1, v2, weight) { return this.addOrRemove(v1, v2, weight, "add") }
	addVertex(vertex) {
	if (this.adjacencyList[vertex]) throw new Error("Vertex already existing")
	this.adjacencyList[vertex] = []
	return this.adjacencyList[vertex]
	}
	//up to here it's all the same as logic explained before in other gists
	/////////////////////////////////////////////////////////////////////////////////////
	//a simple private method to create an object with the keys as all vertices and the value is passed down as an argument
	//the start argument should be the start vertex if we want to make sure that the start vertex has a different value than the rest
	createObjectFromVertices(newValue, start) {
	return Object.fromEntries(
	Object.entries(this.adjacencyList)
	.map(([key, value]) => { return [key, key === start ? 0 : newValue] })
	)
	}
	//it works as follows
	//we define an object or a hash map with all the vertices in the adjacency list of the current graph with the values set to null initially and as the logic continues null will represent the shortest path to it is going through which node
	//meaining, if we have {E: C} in the object, then that means the shortest path to E from whatever the start vertex is, is through the C vertex, and we can check the C vertex to see which way is shortest to it
	//doing that makes a map that gets the shortest way to any vertex from the startin vertex that's passed as an argument
	//so if we check the end vertex in this object and track the vertices shortest path until we reach the start, then this is the shortest path from the start vertex to the end
	//in order to that we'll need to have another object with all the vertices but the values here are set to Infinity this object will have the total distance from start to the key vertex
	//having this object will make us compare the length calculated at the current state with the one in the object and if the new calculated is shorter then we update both object accordingly
	//let's start
	dijkstra(start, end) {
	// we first start with the priority queue
	// by doing that the priority queue that is formed from a min binary heap will sort the smallest weight to the top
	// so when we pop the smallest item from the priority queue if it was the the destination vertex, then any other route would be longer so we stop looping and we get the shortest path
	const q = new PriorityQueue()
	//we create the object of distances with all vertices values set to Infinity except the start set to 0
	const distances = this.createObjectFromVertices(Infinity, start)
	//then we create the prev object that shows through chich previous node is the shortest path going like explained before
	const prev = this.createObjectFromVertices(null)
	//we start by enqueuing the start vertex and its distance, which is 0 (this is just the intitation step, the priority is not required here because it's the first and only item in the queue)
	q.enqueue(start, distances[start])
	//then we start a loop as long as there're items in the queue
	while (q.values.length) {
	//because that's a priority queue if we deuqueue an item then it's the smallest distance vecause it's a min binary heap
	//so we store the smallest value in a variable
	const smallest = q.dequeue().val
	//check smallest to see if it was the the same as the end vertex,
	//if true then any other route would be longer so we stop looping and we get the shortest path, so we break
	if (smallest === end) break
	//if it's not the end then we start looping over all the edges of the vertex
	this.adjacencyList[smallest].forEach(item => {
	//first we calculate the distance of the smallest vertex that was popped from the queue to the current vertex in the edges loop iteration
	//we do that by getting the shortest distance of the smallest that's stored in the the distances object, and we add that to the weight of the current edge that corresponds to both the vertices
	const currentItemDistanceFromStart = distances[smallest] + item.weight
	//compare the distance that's calculated to the one stored in distances object
	//(if this was the first time calculated, then it's getting compared to Infinity which is the initial value and obviously it will be the new minimum anyway, but if it was another calculation ti'll be compared to the previously stored distance)
	const currentItemMinDistanceFromStart = Math.min(distances[item.node], currentItemDistanceFromStart)
	//we check if the new minimum is smaller than the distance stored
	if (currentItemMinDistanceFromStart < distances[item.node]) {
	//if it is smaller, then that's a new smaller distance from the current vertex to the start
	//so we store it as the new value of distance for the current vertex in distances object
	distances[item.node] = currentItemMinDistanceFromStart
	//and we set the prev node that the shortest path is going through to be the current popped smallest item from the queue that we're looping over its edges right now
	prev[item.node] = smallest
	//and then we enqueue the current edge to the queue, with the weight as the shortest current distance from the start
	q.enqueue(item.node, distances[item.node])
	//by doing that after the first iteration of the while loop, we'll have the shortest path is through the start vertex for each nextdoor neighbor and the distances of each is the same as the weight of the edges
	//but this is enquining into the queue so it will have the smallest distance ready, and ti'll scale and keep doing that untill we hit the end vertex
	}
	//if the newly calculated distance is not the smaller one, then we just skip doing anything and go to the next iteration in the while loop
	})
	}
	//this is a simple logic to tradc back the shortest path from the prev object from the start to the end vertex by check through which vertex is the path going through and push it in an array
	//keep iterating over untill we reach the start vertex and we break, so it will result in an array that has the order of vertices in which the shortest path is going through
	const ansArr = [end]
	let current = end
	while (current !== start) {
	const prevItem = prev[current]
	ansArr.push(prevItem)
	current = prevItem
	}
	//return the order of shortest path array
	return ansArr
	}
	}