JSFiddle - React, Tailwind, and code Playground

by shrpne

JavaScript

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

    enqueue(val, priority) {
        this.values.push({ val, priority });
        this.sort(); // This is the inefficient part for large graphs
    }

    dequeue() {
        return this.values.shift();
    }

    sort() {
        this.values.sort((a, b) => a.priority - b.priority);
    }
}

const graph = {}
graph.a = {b: 2, c: 1}
graph.b = {f: 7}
graph.c = {d: 5, e: 2}
graph.d = {f: 2}
graph.e = {f: 1}
graph.f = {g: 1}
graph.g = {}


function dijkstra(graph, startNode, endNode) {
    const distances = {}; // Stores the shortest distance from startNode to each node
    const previous = {};  // Stores the previous node in the shortest path
    const pq = new PriorityQueue(); // Priority queue to manage unvisited nodes

    // Initialize distances: infinity for all nodes except startNode (0)
    for (let node in graph) {
        distances[node] = Infinity;
        previous[node] = null;
    }
    distances[startNode] = 0;

    // Enqueue the start node with priority 0
    pq.enqueue(startNode, 0);

    // Main loop: while there are nodes to visit
    while (pq.values.length) {
        const { val: currentNode, priority: currentDistance } = pq.dequeue();

        // If we reached the end node, we can reconstruct the path
        if (currentNode === endNode) {
            const path = [];
            let temp = endNode;
            while (temp) {
                path.push(temp);
                temp = previous[temp];
            }
            return {
                path: path.reverse(),
                distance: distances[endNode]
            };
        }

        // Skip if we found a shorter path to this node already
        if (currentDistance > distances[currentNode]) {
            continue;
        }

        // Explore neighbors of the current node
        for (let neighbor in graph[currentNode]) {
            const...