Графы

#include <iostream>
#include <vector>
#include <limits>
#include <queue>

using namespace std;

const int INF = numeric_limits<int>::max();

class Graph {
    //ребро
    struct Edge {
        //откуда
        int source;
        //куда
        int destination;
        //вес
        int weight;
    };
    //количество вершин
    int V;
    //матрица смежности(откуда, какие ребра)
    vector<vector<Edge>> adjList;
    //список ребер
    vector<Edge> edges;

public:
    Graph(int V) : V(V) {
        //изменяем размер
        adjList.resize(V);
    }

    //Добавить вершину
    void addEdge(int source, int destination, int weight) {
        Edge edge = { source, destination, weight };
        //относительно конкретной вершины(от которой ребро)
        adjList[source].push_back(edge);
        //просто список ребер
        edges.push_back(edge);
    }
    //добавить вершину
    void addNode() {
        adjList.push_back(vector<Edge>());
        V++;
    }

    //вывод на экран построчной таблицы смежности
    void displayGraph() {
        for (int i = 0; i < V; ++i) {
            cout << "Узел " << i + 1 << " связан с ребром \n";
            for (Edge& edge : adjList[i]) {
                cout << "\tУзел " << edge.destination + 1 << " с весом ребра = " << edge.weight << "\n";
            }
            cout << "\n";
        }
    }

    //Найти Эксцентриситет
    int findEccentricity(int node) {
        vector<int> distances(V, INF);
        distances[node] = 0;
        //очередь
        queue<int> q;
        q.push(node);

        // Стандартная BFS(обход в ширину) для вычисления расстояний от узла до всех остальных узлов
        while (!q.empty()) {
            //достаем первую вершину из очереди
            int u = q.front();
            //достать из очереди
            q.pop();

            for (auto& edge : adjList[u]) {
                //если нашли более короткий путь - обновляем
                if (distances[edge.destination] > distances[u] + edge.weight) {
                    distances[edge.destination] = distances[u] + edge.weight;
                    //вставить в очередь
                    q.push(edge.destination);
                }
            }
        }
        //находим самое большое расстояние в графе
        int eccentricity = 0;
        for (int dist : distances) {
            if (dist != INF) {
                eccentricity = max(eccentricity, dist);
            }
        }

        return eccentricity;
    }

    bool bellmanFord(int source, vector<int>& distances, vector<int>& predecessors) {
        //Делаем массив длинны v и заполняем "бесконечностями"
        distances.assign(V, INF);
        //Делаем массив длинны v и заполняем -1
        predecessors.assign(V, -1);
        distances[source] = 0;

        for (int i = 0; i < V - 1; ++i) {
            for (const Edge& edge : edges) {
                //Если этот проход еще не проверяли(там беск), и путь через вершину короче, чем есть - обновляем
                if (distances[edge.source] != INF && distances[edge.source] + edge.weight < distances[edge.destination]) {
                    distances[edge.destination] = distances[edge.source] + edge.weight;
                    predecessors[edge.destination] = edge.source;
                }
            }
        }

        // Проверка на наличие циклов с отрицательным весом
        for (const Edge& edge : edges) {
            if (distances[edge.source] != INF && distances[edge.source] + edge.weight < distances[edge.destination]) {
                return false; // Граф содержит цикл с отрицательным весом
            }
        }

        return true; // Циклы с отрицательным весом не найдены
    }

    //печатает кратчайшие расстояния
    void printPath(int source, int destination, const vector<int>& predecessors) {
        if (source == destination) {
            cout << source + 1;
            return;
        }
        if (predecessors[destination] == -1) {
            cout << "Путь от " << source + 1 << " до " << destination << " не существует.";
            return;
        }
        printPath(source, predecessors[destination], predecessors);
        cout << " -> " << destination;
    }
};

int main() {
    setlocale(LC_ALL, "Russian");
    int V = 8;
    Graph g(V);
    //создали граф из пунтка 10
    g.addEdge(0, 1, 23);
    g.addEdge(0, 2, 12);
    g.addEdge(1, 0, 23);
    g.addEdge(1, 2, 25);
    g.addEdge(1, 4, 22);
    g.addEdge(1, 7, 35);
    g.addEdge(2, 0, 12);
    g.addEdge(2, 1, 25);
    g.addEdge(2, 3, 18);
    g.addEdge(3, 2, 18);
    g.addEdge(3, 5, 20);
    g.addEdge(4, 1, 22);
    g.addEdge(4, 5, 23);
    g.addEdge(4, 6, 14);
    g.addEdge(5, 3, 20);
    g.addEdge(5, 4, 23);
    g.addEdge(5, 6, 24);
    g.addEdge(6, 4, 14);
    g.addEdge(6, 5, 24);
    g.addEdge(6, 7, 16);
    g.addEdge(7, 1, 35);
    g.addEdge(7, 6, 16);

    //вывели на экран
    g.displayGraph();

    //выбираем первую вершину и относительно нее
    int node = 1;
    //считаем Эксцентриситет
    cout << "Эксцентриситет узла " << node << " составляет: " << g.findEccentricity(node) << endl;

    vector<int> distances;
    vector<int> predecessors;
    //выбираем первую вершину и относительно нее считаем кратчайшие расстояния по Белману-Форду
    int source = 1;
    //если нет отрицательного цикла
    if (g.bellmanFord(source, distances, predecessors)) {
        //выписываем кратчайшие расстояния
        cout << "Кратчайшие пути из узла " << source + 1 << " являются:" << endl;
        for (int i = 0; i < V; ++i) {
            cout << "Расстояние до " << i + 1 << " равно " << distances[i] << " и путь равен: ";
            g.printPath(source, i, predecessors);
            cout << endl;
        }
    }
    else {
        cout << "Граф содержит цикл с отрицательным весом" << endl;
    }

    return 0;
}