#include <iostream>
#include <iomanip>

using namespace std;

const int inf = INT32_MAX; // бесконечно большая величина
const int null = INT32_MIN; // бесконечно маленькая величина

const int n = 15; // кол-во вершин графа

// структура, описывающая ребро графа
struct _edge
{
    int cost;
    int parent1;
    int parent2;
};

int leader[n] = { 0 }; // массив корней поддеревьев

// заполнение ячейки массива корней поддеревьев начальным значением
void make_set(int v)
{
    leader[v] = v;
}

// функция, определяющая принадлежность вершины к поддереву
int find_set(int v)
{
    if (v == leader[v])
        return v;
    return leader[v] = find_set(leader[v]); // возвращает корень поддерева
}

// функция объединения поддеревьев
int union_sets(int a, int b)
{
    a = find_set(a);
    b = find_set(b);
    if (a != b)
    {
        leader[b] = a;
        return 1;
    }
    return 0;
}

//алгоритм Флойда-Уоршелла поиска кратчайших путей
void Floyd_Warshall(int matrix[][n], int(*shortest)[n][n][n + 1], int(*pred)[n][n][n + 1])
{
    // заполняем матрицу кратчайших путей и матрицу предшествующих вершин начальными значениями
    for (int u = 0; u < n; u++)
        for (int v = 0; v < n; v++)
        {
            (*shortest)[u][v][0] = matrix[u][v];
            if ((matrix[u][v] == inf) || (matrix[u][v] == 0)) (*pred)[u][v][0] = NULL;
            else (*pred)[u][v][0] = u;
        }

    for (int x = 1; x < n + 1; x++)
    {
        // перезаписываем массив крачайших путей с х-1 итерации на х
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                (*shortest)[i][j][x] = (*shortest)[i][j][x - 1];

        // проходим по всем элементам матрицы на х-ой итерации
        for (int u = 0; u < n; u++)
            for (int v = 0; v < n; v++)
            {
                // если найден более короткий путь, то записываем его в массив shortest
                if (((*shortest)[u][v][x] > (((*shortest)[u][x - 1][x - 1] + (*shortest)[x - 1][v][x - 1]))) && ((((*shortest)[u][x - 1][x - 1]) != inf) && (((*shortest)[x - 1][v][x - 1]) != inf)))
                {

                    (*shortest)[u][v][x] = (*shortest)[u][x - 1][x - 1] + (*shortest)[x - 1][v][x - 1];
                    (*pred)[u][v][x] = (*pred)[x - 1][v][x - 1];
                }
                // если более короткий путь не найден, то записываем значение из массива предыдущей итерации в массив shortest и pred текущей итерации
                else
                {
                    (*shortest)[u][v][x] = (*shortest)[u][v][x - 1];
                    (*pred)[u][v][x] = (*pred)[u][v][x - 1];
                }
            }
    }
}

// функция форматированного вывода матрицы shortest кратчайших путей
void outputFW(int shortest[n][n][n + 1], int pred[n][n][n + 1])
{
    for (int x = 0; x < n + 1; x++)
    {
        cout << "\n****************************************************\n";
        cout << "\nx = " << x << "\n";

        cout << "\nSHORTEST: \n\n";
        for (int u = 0; u < n; u++)
        {
            for (int v = 0; v < n; v++)
            {
                if (shortest[u][v][x] == inf) cout << setw(8) << "inf" << " ";
                else cout << setw(8) << shortest[u][v][x] << " ";
            }
            cout << "\n";
        }

        cout << "\nPRED: \n\n";
        for (int u = 0; u < n; u++)
        {
            for (int v = 0; v < n; v++)
            {
                if (pred[u][v][x] == null) cout << setw(8) << "null" << " ";
                else cout << setw(8) << pred[u][v][x] << " ";
            }
            cout << "\n";
        }
    }
    cout << "\n****************************************************\n\n";
}

// форматированный вывод матрицы смежности графа
void outputMatrix(int matrix[][n])
{
    for (int u = 0; u < n; u++)
    {
        for (int v = 0; v < n; v++)
        {
            if (matrix[u][v] == inf) cout << setw(8) << "inf" << " ";
            else cout << setw(8) << matrix[u][v] << " ";
        }
        cout << "\n";
    }
}

// функция перевода графа из ориентированного в неориентированный и подсчета кол-ва ребер
void makeGraphUnoriented(int(*matrix)[n][n], int* RealEdgeCount)
{
    for (int u = 0; u < n; u++)
    {
        for (int v = u + 1; v < n; v++)
        {
            if (((*matrix)[u][v] == inf) && ((*matrix)[v][u] != inf))
            {
                (*matrix)[u][v] = (*matrix)[v][u];
                (*RealEdgeCount)++;
            }

            if (((*matrix)[v][u] == inf) && ((*matrix)[u][v] != inf))
            {
                (*matrix)[v][u] = (*matrix)[u][v];
                (*RealEdgeCount)++;
            }

        }
    }
}

// сортировка Шелла
void ShellSort(_edge **edge, int RealEdgeCount)
{
    int h = 0;

    while (h < RealEdgeCount / 3)
    {
        h = 3 * h + 1;
    }

    for (h; h > 0; h = (h - 1) / 3)
    {
        for (int i = h; i < RealEdgeCount; i++)
        {
            int j = i;
            _edge tmp = (*edge)[i];

            for (j = i; j >= h && (*edge)[j - h].cost > tmp.cost; j -= h)
            {
                (*edge)[j] = (*edge)[j - h];

            }
            (*edge)[j] = tmp;
        }
    }

    return;
}

// функция алгоритма Краскала построения остовного дерева графа
void graphKruskalAlgorithm(int matrix [n][n], int RealEdgeCount)
{
    int newMatrix[n][n];

    for (int u = 0; u < n; u++)
        for (int v = 0; v < n; v++)
            if (u == v) newMatrix[u][v] = 0;
            else newMatrix[u][v] = inf;

    //outputMatrix(newMatrix);

    int i = 0;

    cout << "\n\nАлгоритм Краскала\n";

    _edge* edge = new _edge[RealEdgeCount];

    for (int u = 0; u < n; u++)
    {
        for (int v = u + 1; v < n; v++)
        {
            if(matrix[u][v]!=inf)
            {
                edge[i].cost = matrix[u][v];
                edge[i].parent1 = u;
                edge[i].parent2 = v;
                i++;
            }

        }
    }
    cout << "\nНеотсортированные ребра: \n";
    for (int k = 0; k < RealEdgeCount; k++)
        cout << "\tРебро " << k + 1 << ": Cost = " << edge[k].cost << ", 1-я вершина = " << edge[k].parent1 + 1 << ", 2-я вершина = " << edge[k].parent2 + 1 << "\n";
    cout << "\n";

    ShellSort(&edge, RealEdgeCount);

    cout << "\nОтсортированные ребра: \n";
    for (int k = 0; k < RealEdgeCount; k++)
        cout << "\tРебро " << k + 1 << ": Вес = " << edge[k].cost << ", 1-я вершина = " << edge[k].parent1 + 1 << ", 2-я вершина = " << edge[k].parent2 + 1 << "\n";
    cout << "\n";

    // заполнение массива корней поддеревьев начальными значениями
    for (i = 0; i < n; i++)
    {
        make_set(i);
    }

    // заполнение матрицы смежности для остовного дерева графа
    for (i = 0; i < RealEdgeCount; i++)
    {
        if (edge[i].cost == inf) continue;
        if (union_sets(edge[i].parent1, edge[i].parent2) == 1)
        {
            newMatrix[edge[i].parent1][edge[i].parent2] = edge[i].cost;
            newMatrix[edge[i].parent2][edge[i].parent1] = edge[i].cost;
        }
    }

    // копирование элементов полученной матрицы в исходную
    for (int u = 0; u < n; u++)
        for (int v = 0; v < n; v++)
            matrix[u][v] = newMatrix[u][v];
}

int main()
{

    setlocale(LC_ALL, "RUS");
    system("color F0");

    int shortest[n][n][n + 1] = { 0 }; // массив матриц кратчайших путей найденных на каждой из итераций
    int pred[n][n][n + 1] = { 0 }; // массив матриц предшествующих вершин найденных на каждой из итераций

    int RealEdgeCount = 0; // счетчик кол-ва ребер

    int matrix[n][n] =
    {
    {   0,  -1, inf,   2, inf, inf, inf, inf, inf, inf,  8, inf, inf, inf, inf },
    { inf,   0, inf,   3, inf,  10, inf, inf, inf, inf, inf, inf, inf, inf, inf },
    { inf,   4,   0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf },
    { inf, inf, inf,   0, inf, inf,  13, inf, inf, inf,  -7, inf, inf, inf, inf },
    { inf, inf, inf, inf,   0, inf, inf,   3, inf,  11, inf, inf, inf, inf, inf },
    { inf, inf, inf, inf, inf,   0, inf, inf,  18, inf, inf, inf, inf, inf, inf },
    { inf, inf, inf, inf, inf, inf,   0, inf, inf,  15, inf, inf, inf, inf, inf },
    { inf, inf, inf, inf, inf,  -8, inf,  0, inf, inf, inf, inf, inf, inf, inf },
    { inf, inf, inf, inf, inf, inf, inf, inf,   0, inf, inf, inf, inf, inf, inf },
    { inf, inf, inf, inf, inf, inf, inf, inf,  19,   0, inf, inf, inf, inf, inf },
    { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,   0, inf, inf,   2,  11 },
    { inf, inf, inf, inf,  16, inf, inf, inf, inf, inf, inf,   0,  12, inf, inf },
    { inf, inf, inf, inf, inf, inf,  17, inf, inf, inf, inf, inf,   0, inf, inf },
    { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,   0,   9 },
    { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,   1,  -7, inf,   0 }
    };

    //алгоритм Флойда-Уоршелла поиска кратчайших путей
    Floyd_Warshall(matrix, &shortest, &pred);

    // форматированный вывод массивов матриц shortest и pred
    outputFW(shortest, pred);

    cout << "\nДелаем граф неориентированным...\n\n";

    // функция перевода графа из ориентированного в неориентированный и подсчета кол-ва ребер
    makeGraphUnoriented(&matrix, &RealEdgeCount);

    cout << "\nПреобразованная матрица графа: \n\n";

    // функция форматированного вывода матрицы смежности графа
    outputMatrix(matrix);

    // функция алгоритма Краскала построения остовного дерева графа
    graphKruskalAlgorithm(matrix, RealEdgeCount);

    cout << "\nРезультирующая матрица графа: \n\n";

    outputMatrix(matrix);

    cout << "\n";

    system("pause");
}