8. Веса IV а (Дейкстра) (15 задание)

void Dijkstra(string start, map<string, int>& distances, map<string, string>& previous) {
        for (const auto& vertex : this->AdjList) {
            distances[vertex.first] = INT_MAX;
        }
        distances[start] = 0;

        priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> pq;
        pq.push({ 0, start });

        while (!pq.empty()) {
            string current = pq.top().second;
            int dist = pq.top().first;
            pq.pop();

            if (dist > distances[current]) continue;

            // Рассматриваем всех соседей текущей вершины
            for (const auto& neighbor : this->AdjList[current]) {
                string next = neighbor.first;
                int weight = neighbor.second;
                int newDist = dist + weight;

                if (newDist < distances[next]) {
                    distances[next] = newDist;
                    previous[next] = current;
                    pq.push({ newDist, next });
                }
            }
        }
    }

    void reconstructPath(map<string, string>& previous, string start, string end, vector<string>& path) {
        for (string i = end; i != start; i = previous[i]) {
            path.push_back(i);
        }
        path.push_back(start);
        reverse(path.begin(), path.end());
    }

    void Task8(string u1, string u2, string v) {
        map<string, int> distU1, distU2;
        map<string, string> prevU1, prevU2;

        Dijkstra(u1, distU1, prevU1);
        Dijkstra(u2, distU2, prevU2);

        if (distU1[v] == INT_MAX || distU2[v] == INT_MAX) {
            cout << "Пути из одной или обеих вершин до " << v << " не существуют." << endl;
            return;
        }

        vector<string> pathU1, pathU2;
        reconstructPath(prevU1, u1, v, pathU1);
        reconstructPath(prevU2, u2, v, pathU2);

        cout << "Кратчайший путь от " << u1 << " до " << v << ": ";
        for (const auto& node : pathU1) {
            cout << node << " ";
        }
        cout << "\nДлина пути: " << distU1[v] << endl;

        cout << "Кратчайший путь от " << u2 << " до " << v << ": ";
        for (const auto& node : pathU2) {
            cout << node << " ";
        }
        cout << "\nДлина пути: " << distU2[v] << endl;

        cout << "\n";
    }

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <vector>
#include <list>
#include <map>
#include <locale>
#include <windows.h>
#include "Graph.h"

using namespace std;

int main() {
    setlocale(LC_ALL, "Russian");
    SetConsoleOutputCP(CP_UTF8);
    map<string, Graph> graphs;

    string с = "prim3.txt";
    Graph g;
    g.loadFromFile(с);
    graphs[с] = g;

    string u1, u2, v;
    cout << "введите вершины u1 u2 и v:\n";
    cin >> u1 >> u2 >> v;

    cout << "Задание 8\n";
    g.Task8(u1, u2, v);
    cout << "\n";