10. Веса IV c (Беллмана-Форда) (12 задание)

void Task10(string u, string v) {
        if (!ExistVertex(u) || !ExistVertex(v)) {
            cout << "Одна или обе вершины не существуют." << endl;
            return;
        }

        map<string, int> distances;
        map<string, string> pred;
        for (const auto& vertex : AdjList) {
            distances[vertex.first] = INF;
            pred[vertex.first] = "";
        }
        distances[u] = 0;

        // алгоритм Беллмана-Форда
        int V = CountVertices();
        for (int i = 0; i < V - 1; ++i) {
            for (const auto& u : AdjList) {
                for (const auto& v : u.second) {
                    string from = u.first;
                    string to = v.first;
                    int weight = v.second;

                    if (distances[from] < INF && distances[from] + weight < distances[to]) {
                        distances[to] = distances[from] + weight;
                        pred[to] = from;
                    }
                }
            }
        }

        for (const auto& u : AdjList) {
            for (const auto& v : u.second) {
                string from = u.first;
                string to = v.first;
                int weight = v.second;

                if (distances[from] < INF && distances[from] + weight < distances[to]) {
                    cout << "Граф содержит отрицательный цикл!" << endl;
                    return;
                }
            }
        }


        if (distances[v] == INF) {
            cout << "Нет пути из " << u << " в " << v << "." << endl;
            return;
        }

        vector<string> path;
        for (string at = v; at != ""; at = pred[at]) {
            path.push_back(at);
        }
        reverse(path.begin(), path.end());

        cout << "Кратчайший путь из " << u << " в " << v << ": ";
        for (size_t i = 0; i < path.size(); ++i) {
            cout << path[i];
            if (i < path.size() - 1) cout << " -> ";
        }
        cout << "\nДлина пути: " << distances[v] << "\n";
    }


//main.cpp
#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 v;
    cout << "введите вершины u1 и v:\n";
    cin >> u1 >> v;

    cout << "Задание 10\n";
    g.Task10(u1, v);

}