Data Structures and Algorithms in JavaScript: Dijkstra’s Shortest Path Algorithm

TheTechnoCult

·

Follow

1 min read

·

Jan 2, 2024

--

Listen

Share

class PriorityQueue {
    constructor() {
        this.collection = []
    }

    enqueue(element){
        if (this.isEmpty()) { 
            this.collection.push(element)
        } else {
            let added = false
            for (let i = 1; i <= this.collection.length; i++){
                if (element[1] < this.collection[i-1][1]) { 
                    this.collection.splice(i-1, 0, element)
                    added = true
                    break
                }
            }
            if (!added){
                this.collection.push(element)
            }
        }
    }

    dequeue() {
        let value = this.collection.shift()
        return value
    }

    isEmpty() {
        return (this.collection.length === 0) 
    }
}

function dijkstra(graph, startNode, endNode) {
    let distances = {}
    let prev = {}
    let pq = new PriorityQueue()

    // Initialization: set every distance to Infinity and previous node to null
    for (let node in graph) {
        distances[node] = Infinity
        prev[node] = null
    }

    distances[startNode] = 0
    pq.enqueue([startNode, 0])

    while (!pq.isEmpty()) {
        let [currentNode, currentDistance] = pq.dequeue()

        // Early exit if we reach the end node
        if (currentNode === endNode) break

        for (let neighbor in graph[currentNode]) {
            let newDistance = currentDistance + graph[currentNode][neighbor]

            if (newDistance < distances[neighbor]) {
                distances[neighbor] = newDistance
                prev[neighbor] = currentNode
                pq.enqueue([neighbor, newDistance])
            }
        }
    }

    // Reconstruct the shortest path
    let path = []
    let current = endNode

    while (current !== startNode) {
        path.unshift(current)
        current = prev[current]
    }

    path.unshift(startNode)
    return path
}

// Example usage
const graph = {
    A: {B: 1, C: 4},
    B: {A: 1, C: 2, D: 5},
    C: {A: 4, B: 2, D: 1},
    D: {B: 5, C: 1}
};

console.log(dijkstra(graph, 'A', 'D')) // Output will be the shortest path from A to D