#include <time.h>
#include <random>
#include <math.h>
#include <iostream>
#include <vector>

#define inf 100000

using namespace std;

// структура для хранения графа в виде ребер
// тут:
// u - левый узел ребра
// v - правый узел ребра
// w - соответственно вес ребра
struct Rebra{
    int rightUzel, leftUzel, weight;
};

const int Vmax = 1000; // максимально возможное количество кратчайших путей (берем заведеомо большее число чтобы все уместилось)
const int Emax = Vmax*(Vmax - 1) / 2; // максимальное количество ребер
Rebra rebro[Emax]; //
// массив для хранения кратчайших путей из начального узла во все остальные
// индекс в первых квадратных скобках тут обозначает № узла
// а индексы во вторых скобках имеют смысл:
// 0 - минимальный вес от начального узла до узла который указан в первых скобках кважратных
// 1 - № узла из которого пришли в данный узел
int distanc[Vmax];
int izKakogoUzla[Vmax];
int width_belt, arr[1000][1000];
int i, j, n, kolichestvoReber, p, start, endnode;

//алгоритм Беллмана-Форда
// n - количество узлов
// s - стартовая вершина
void bellman_ford(int n, int s)
{
    // присваиваем всем значениям массива для хранения минимальых дистанций огромное число (нужно для корректной работы алгоритма нахождения минимума)
    for (i = 0; i < n; i++)
    {
        distanc[i] = inf;
        izKakogoUzla[i] = -1;
    }

    // стартовая вершина имеет нулевой вес (с неё же начинаем все таки)
    distanc[s] = 0;

    // собственно основной алгоритм
    for (i = 0; i<n - 1; i++)
    {
        for (j = 0; j<kolichestvoReber; j++)
        {
            // если [путь до A]+B лучше чем уже имеющейся минимальный путь, то записываем этот путь в distance
            if (distanc[rebro[j].leftUzel] + rebro[j].weight < distanc[rebro[j].rightUzel])
            {
                distanc[rebro[j].rightUzel] = distanc[rebro[j].leftUzel] + rebro[j].weight;
                izKakogoUzla[rebro[j].rightUzel] = rebro[j].leftUzel; // записываем откуда пришли
            }
        }
    }

    cout << "Список кратчайших путей:" << endl;
    for (i = 1; i < n; i++)
    {
        if (distanc[i] == inf)
            cout << start << "->" << i + 1 << "=" << "Нету пути..." << endl;
        else
        {
            vector<int> path;
            for (int cur = i; cur != -1; cur = izKakogoUzla[cur])
                path.push_back(cur);
            reverse(path.begin(), path.end());

            cout << "Путь: " << path[0];
            for (size_t i = 1; i < path.size(); ++i)
                cout << "->" << path[i];
            cout << " Вес: " << distanc[i] << endl;
        }
    }
}

//главная функция
void main()
{
    // устанавливаем кодировку русскую для консоли
    setlocale(LC_ALL, "Rus");

    std::default_random_engine generator;
    generator.seed(time(NULL)); // инициализируем генератор случайных чисел
    // тут 10 это среднее число для генерации случайных чисел
    // 5 это дисперсия(разброс) генерации чисел относительно среднего числа (+-10)
    std::normal_distribution<> rnd(10, 5); // нормальное распределение

    cout << "Количество вершин > "; cin >> n;
    cout << "Ширина ленточной матрицы > "; cin >> width_belt;
    cout << "Конечная вершина > "; cin >> endnode;
    cout << "Стартовая вершина > "; cin >> start;

    cout << "Сгенерированная ленточная матрица" << endl;
    for (int i = 1; i < n; i++)
    {
        for (int j = i + 1; j <= i + width_belt; j++)
        {
            // не заполнять элементы за границей массива
            if (j >= n)
                break;

            // заполняем по строчно
            arr[i][j] = floor(rnd(generator));
            // по столбцу
            arr[j][i] = floor(rnd(generator));

        }
    }

    // задаем ограничени¤
    arr[0][1] = floor(rnd(generator)); // 1 св¤зан с 2
    arr[0][3] = floor(rnd(generator)); // 1 св¤зан с 4
    arr[3][0] = floor(rnd(generator)); // 1 св¤зан с 2
    arr[1][0] = floor(rnd(generator)); // 1 св¤зан с 4

    // выводим сгенерированный массив
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }

    // переводим матрицу в массив ребер для более удобной работы в дальнейшем
    kolichestvoReber = 0;
    cout << "Ребра:" << endl;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (arr[i][j] != 0)
            {
                rebro[kolichestvoReber].leftUzel = i;
                rebro[kolichestvoReber].rightUzel = j;
                rebro[kolichestvoReber].weight = arr[i][j];
                kolichestvoReber++;
                cout << "Вес ребра " << i + 1 << "->" << j + 1 << "=" << arr[i][j] << endl;
            }
        }
    }

    // переходим непосредственно к алгоритму вычисления кратчайшего пути
    bellman_ford(n, start);

    // чтобы программа сразу же не закрывалась
    system("pause>>void");
}