graf

//Пример входного файла "graph.txt":
//Количество вершин
//Исходная вершина
//u v weight
//u v weight
//
//где u - исходная вершина, v - конечная, weight - вес ребра


#include <iostream>
#include <fstream>
#include <vector>
#include <limits>

using namespace std;

int INF = numeric_limits<int>::max(); // Значение "бесконечность"

// Структура для представления ребра графа
struct Edge
{
    int destination; // Вершина, в которую ведет ребро
    int weight;      // Вес ребра
};

void floyd_warshall_algorithm(vector<vector<Edge>>& graph, int number_of_vertices, vector<vector<int>>& distances)
{
    // Элементы на диагонали матрицы расстояний равны 0
    for (int i = 0; i < number_of_vertices; i++)
        distances[i][i] = 0;

    // Заполнение матрицы расстояний из графа
    for (int u = 0; u < number_of_vertices; u++)
        for (Edge edge : graph[u])
            distances[u][edge.destination] = edge.weight;

    // Вычисление кратчайших путей между всеми парами вершин
    for (int k = 0; k < number_of_vertices; k++)
        for (int i = 0; i < number_of_vertices; i++)
            for (int j = 0; j < number_of_vertices; j++)
                // Если путь через вершину k короче текущего пути, обновляем его
                if (distances[i][k] != INF && distances[k][j] != INF && distances[i][k] + distances[k][j] < distances[i][j])
                        distances[i][j] = distances[i][k] + distances[k][j];
}

// Обход графа в глубину
void DFS(vector<vector<Edge>>& graph, int vertex, vector<bool>& visited)
{
    visited[vertex] = true; // Помечаем текущую вершину как посещенную
    cout << vertex << " "; // Выводим текущую вершину

    // Рекурсивно обходим все соседние вершины
    for (Edge edge : graph[vertex])
    {
        int next_vertex = edge.destination;
        if (!visited[next_vertex])
        {
            DFS(graph, next_vertex, visited);
        }
    }
}


int main()
{
    setlocale(LC_ALL, "rus");
    ifstream file("graph.txt");
    if (!file)
    {
        cout << "Не удалось открыть файл." << endl;
        return -1;
    }

    int number_of_vertices;
    file >> number_of_vertices; // Считываем количество вершин графа

    vector<vector<Edge>> graph(number_of_vertices); // Граф, представленный списком смежности

    int source; // Исходная вершина
    file >> source;

    // Считываем данные о ребрах графа из файла
    int u, v, weight;
    while (file >> u >> v >> weight)
    {
        graph[u].push_back({ v, weight });
    }

    file.close();

    // Инициализация матрицы расстояний
    vector<vector<int>> distances(number_of_vertices, vector<int>(number_of_vertices, INF));
    floyd_warshall_algorithm(graph, number_of_vertices, distances);

    // Вывод кратчайших путей
    cout << ' ' << '\t';
    for (int i = 0; i < number_of_vertices; i++)
        cout << i << '\t';
    cout << endl << endl;
    for (int i = 0; i < number_of_vertices; i++)
    {
        cout << i << '\t';
        for (int j = 0; j < number_of_vertices; j++)
        {
            if (distances[i][j] == INF)
            {
                cout << "нет пути" << '\t';
            }
            else
            {
                cout << distances[i][j] << '\t';
            }
        }
        cout << endl;
    }

    cout << endl;
    cout << "//////////////////////////////" << endl;
    cout << endl;

    cout << "Обход в глубину: ";
    vector<bool> visited(number_of_vertices, false);
    DFS(graph, source, visited);
    cout << endl;

    return 0;
}