9. Веса IV b (Флойда-Уоршелла) (17 задание)

void Task9() {
        vector<string> vertices;
        for (const auto& vertex : AdjList) {
            vertices.push_back(vertex.first);
        }

        map<string, map<string, int>> dist;
        map<string, map<string, string>> next;
        for (const auto& u : vertices) {
            for (const auto& v : vertices) {
                if (u == v) {
                    dist[u][v] = 0;
                    next[u][v] = v;
                }
                else if (ExistEdge(u, v)) {
                    dist[u][v] = AdjList[u][v];
                    next[u][v] = v;
                }
                else {
                    dist[u][v] = INF;
                    next[u][v] = "";
                }
            }
        }

        // алгоритм Флойда-Уоршелла
        for (const auto& k : vertices) {
            for (const auto& i : vertices) {
                for (const auto& j : vertices) {
                    if (dist[i][k] < INF && dist[k][j] < INF) {
                        if (dist[i][j] > dist[i][k] + dist[k][j]) {
                            dist[i][j] = dist[i][k] + dist[k][j];
                            next[i][j] = next[i][k]; // Обновляем путь
                        }
                    }
                }
            }
        }

        cout << "Кратчайшие пути для всех пар вершин:" << endl;
        for (const auto& u : vertices) {
            for (const auto& v : vertices) {
                if (u != v) {
                    if (dist[u][v] == INF) {
                        cout << "Нет пути из " << u << " в " << v << endl;
                    }
                    else {
                        cout << "Кратчайший путь из " << u << " в " << v << " (длина " << dist[u][v] << "): ";
                        string current = u;
                        while (current != v) {
                            cout << current << " -> ";
                            current = next[current][v];
                        }
                        cout << v << endl;
                    }
                }
            }
        }

        cout << "\nМатрица кратчайших расстояний между всеми парами вершин:" << endl;
        for (const auto& i : vertices) {
            for (const auto& j : vertices) {
                if (dist[i][j] == INF) {
                    cout << "INF ";
                }
                else {
                    cout << dist[i][j] << " ";
                }
            }
            cout << endl;
        }
    }


//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;

    cout << "Задание 9\n";
    g.Task9();
    cout << "\n";
}