dijkstraShortestWay.js - there is a function which uses dijkstra algorithm to find the shortest way in graph

dijkstraShortestWay.js

/**
 * This function uses dijkstra algorithm to find the shortest way in graph.
 * So for this function to work properly, graph must be directed and acyclic with positive weights only
 */

export default function findShortestWayIn(graph) {
    const minimumCosts = {};
    let queue = [{}];
    const visitedPointsFromSpecificParent = {}; // to detect a cycle in a graph
    return {
        initQueue(startPoint) {
            const firstNextPoints = graph[startPoint];
            if (!firstNextPoints) return null;
            const newQueue = [];
            for (let i = 0, len = firstNextPoints.length; i < len; i++) {
                const firstNextPointWithParent = {
                    name: graph[startPoint][i],
                    parent: startPoint
                }
                newQueue.push(firstNextPointWithParent);
            }
            let z = queue.length;
            for (let i = 0; i < newQueue.length; i++) {
                queue[z++] = newQueue[i];
            }

        },
        initMinimumCosts(startPoint) {
            minimumCosts[startPoint] = 0;
        },
        from(startPoint) {
            this.initQueue(startPoint);
            this.initMinimumCosts(startPoint);
            return {
                to(endPoint) {
                    return {
                        withCosts(costs) {
                            if (queue.length === 0) {
                                if (minimumCosts[endPoint]) return minimumCosts[endPoint];
                                else return null;
                            }

                            for (let i = 0, len = queue.length; i < len; i++) {
                                const currentNextPoint = queue[i];
                                const nameOfCurrentNextPoint = currentNextPoint['name'];
                                const parentOfCurrentNextPoint = currentNextPoint['parent'];
                                const currentCost = costs[parentOfCurrentNextPoint + ' ' + nameOfCurrentNextPoint];

                                if (typeof minimumCosts[nameOfCurrentNextPoint] === "undefined") {
                                    minimumCosts[nameOfCurrentNextPoint] = minimumCosts[parentOfCurrentNextPoint] + currentCost;
                                } else {
                                    if (minimumCosts[nameOfCurrentNextPoint] > minimumCosts[parentOfCurrentNextPoint] + currentCost) {
                                        minimumCosts[nameOfCurrentNextPoint] = minimumCosts[parentOfCurrentNextPoint] + currentCost;
                                    } else continue;
                                }
                            }

                            this.updateVisitedPoints(queue);
                            this.updateQueue(queue);
                            return this.withCosts(costs);
                        },
                        updateVisitedPoints(queue) {
                            for (let i = 0, len = queue.length; i < len; i++) {
                                const nextPoint = queue[i]['name'];
                                const parentOfNextPoint = queue[i]['parent'];

                                visitedPointsFromSpecificParent[parentOfNextPoint + ' ' + nextPoint] = true;
                            }
                        },
                        updateQueue(queue) {
                            const newQueue = [];
                            const queueLength = queue.length;
                            for (let i = queueLength - 1; i >= 0; i--) {  
                                if (!queue[i]) continue;                            
                                const nextPoint = queue[i]['name'];
                                const furtherPoints = graph[nextPoint];
                                const furtherPointsLength = (furtherPoints ? furtherPoints.length : null);
                                if (!furtherPointsLength) {
                                    if (queue.length === 1) queue.pop();
                                    else continue;
                                }
                                for (let z = furtherPointsLength - 1; z >= 0; z--) {
                                    const furtherPoint = furtherPoints[z];
                                    if(visitedPointsFromSpecificParent[nextPoint + ' ' + furtherPoint]) {
                                        queue.pop();
                                        continue;
                                    }
                                    const furtherPointWithNextPoint = {
                                        name: furtherPoint,
                                        parent: nextPoint
                                    }
                                    
                                    queue.pop();
                                    newQueue.push(furtherPointWithNextPoint);
                                } 
                            }

                            for (let i = 0; i < newQueue.length; i++) {
                                queue.push(newQueue[i]);
                            }
                        }
                    }
                }
            }
        }
    }
}

// Example of usage
// const graphRoutes = {};
// graphRoutes["A"] = ["B", "C"];
// graphRoutes["B"] = ["D", "F"];
// graphRoutes["C"] = ["B", "F"];
// graphRoutes["D"] = ["E", "F"];
// graphRoutes["F"] = ["E"];
// graphRoutes["E"] = [];

// const costsInGraphRoutes = {};
// costsInGraphRoutes['A B'] = 5;
// costsInGraphRoutes['A C'] = 2;
// costsInGraphRoutes['B D'] = 7;
// costsInGraphRoutes['B F'] = 2;
// costsInGraphRoutes['C B'] = 8;
// costsInGraphRoutes['C F'] = 7;
// costsInGraphRoutes['D E'] = 3;
// costsInGraphRoutes['D F'] = 6;
// costsInGraphRoutes['F E'] = 1;

// console.log(findShortestWayIn(graphRoutes).from("A").to("E").withCosts(costsInGraphRoutes));