class MetroGraph {
    constructor() {
        this.stations = {};
    }

    addStation(stationName) {
        this.stations[stationName] = {};
    }

    addConnection(stationA, stationB, time) {
        this.stations[stationA][stationB] = time;
        this.stations[stationB][stationA] = time;
    }

    dijkstraWithMultiplePaths(startStation, endStation, numberOfPaths = 3) {
        const paths = [];

        for (let pathNumber = 0; pathNumber < numberOfPaths; pathNumber++) {
            const distances = {};
            const visited = {};
            const path = {};

            // Инициализация начальных расстояний и пути
            for (const station in this.stations) {
                distances[station] = Infinity;
                visited[station] = false;
                path[station] = null;
            }

            distances[startStation] = 0;

            // Шаги алгоритма Дейкстры
            while (true) {
                let currentStation = null;
                let currentDistance = Infinity;

                // Находим ближайшую непосещенную станцию
                for (const station in this.stations) {
                    if (!visited[station] && distances[station] < currentDistance) {
                        currentStation = station;
                        currentDistance = distances[station];
                    }
                }

                // Если все станции посещены, выходим из цикла
                if (currentStation === null) break;

                // Посещаем текущую станцию
                visited[currentStation] = true;

                // Обновляем расстояния до соседних станций
                for (const neighborStation in this.stations[currentStation]) {
                    const timeToNeighbor = this.stations[currentStation][neighborStation];
                    const totalDistance = distances[currentStation] + timeToNeighbor;

                    if (totalDistance < distances[neighborStation]) {
                        distances[neighborStation] = totalDistance;
                        path[neighborStation] = currentStation;
                    }
                }
            }

            // Восстановление пути
            const pathResult = [endStation];
            let current = endStation;

            while (current !== startStation) {
                const prevStation = path[current];
                pathResult.unshift(prevStation);
                current = prevStation;
            }

            paths.push({
                distance: distances[endStation],
                path: pathResult,
            });
        }

        // Сортировка путей по длине
        paths.sort((a, b) => a.distance - b.distance);

        return paths;
    }

    dijkstra(startStation, endStation) {
        const distances = {};
        const visited = {};
        const path = {};

        // Инициализация начальных расстояний и пути
        for (const station in this.stations) {
            distances[station] = Infinity;
            visited[station] = false;
            path[station] = null;
        }

        distances[startStation] = 0;

        // Шаги алгоритма Дейкстры
        while (true) {
            let currentStation = null;
            let currentDistance = Infinity;

            // Находим ближайшую непосещенную станцию
            for (const station in this.stations) {
                if (!visited[station] && distances[station] < currentDistance) {
                    currentStation = station;
                    currentDistance = distances[station];
                }
            }

            // Если все станции посещены, выходим из цикла
            if (currentStation === null) break;

            // Посещаем текущую станцию
            visited[currentStation] = true;

            // Обновляем расстояния до соседних станций
            for (const neighborStation in this.stations[currentStation]) {
                const timeToNeighbor = this.stations[currentStation][neighborStation];
                const totalDistance = distances[currentStation] + timeToNeighbor;

                if (totalDistance < distances[neighborStation]) {
                    distances[neighborStation] = totalDistance;
                    path[neighborStation] = currentStation;
                }
            }
        }

        // Восстановление пути
        const pathResult = [endStation];
        let current = endStation;

        while (current !== startStation) {
            const prevStation = path[current];
            pathResult.unshift(prevStation);
            current = prevStation;
        }

        return {
            distance: distances[endStation],
            path: pathResult,
        };
    }
}


// Пример использования
const metro = new MetroGraph();

metro.addStation("A");
metro.addStation("B");
metro.addStation("C");
metro.addStation("D");

metro.addConnection("A", "B", 5);
metro.addConnection("B", "C", 3);
metro.addConnection("C", "D", 7);
metro.addConnection("A", "D", 20);

const result = metro.dijkstraWithMultiplePaths("A", "D");

console.log("Result:", result);