Dijkstra's Algorithm

#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <windows.h>

using namespace std;

bool put(bool put_b, int pk, int* put_temp_metka, int** VES, int V)
{
    if ((put_b == true && put_temp_metka[pk] != 1))
    {
        int* temp_x = new int[V];
        int k = -1;
        for (int j = 0; j < V - 1; j++)
        {
            if (VES[j][put_temp_metka[pk] - 1] > 0 && VES[j][put_temp_metka[pk] - 1] < 100)
            {
                k++;
                temp_x[k] = j;
            }
        }
        int temp_k = k;
        if (temp_k>0)
        {
            while (temp_k > 0)
            {
                bool flag = false;
                for (int i = 0; i <= pk; i++)
                {
                    for (int j = 0; j <= pk; j++)
                    {
                        if (put_temp_metka[i] != put_temp_metka[j])
                            flag = true;
                        else
                        {
                            flag = false;
                            break;
                        }
                    }
                }
                if (flag == true)
                {
                    pk++;
                    put_temp_metka[pk] = temp_x[temp_k] + 1;
                    put_b = put(put, pk, put_temp_metka, VES, V);
                    if (put_temp_metka[pk] == put_temp_metka[pk - 1])
                        return false;
                    if (put == false)
                        put_b = true;
                    else if (put_b == true)
                    {
                        return true;
                    }
                    temp_k--;
                }
                else
                {
                    temp_k--;
                }

            }
        }
        if (temp_k == 0)
        {
            pk++;
            put_temp_metka[pk] = temp_x[0] + 1;
        }
        if (put_temp_metka[pk] != put_temp_metka[pk - 1] && k != -1)
        {
            put_b = true;
        }
        else
        {
            put_b = false;
        }
        return put(put_b, pk, put_temp_metka, VES, V);
    }
    else
        return put_b;
    /////////////////////////////////
}

int main()
{
    while (1)
    {
        setlocale(0, "Russian");
        SetConsoleCP(1251);
        SetConsoleOutputCP(1251);
        int V;
        cout << "Введите размерность графа: ";
        while (!(cin >> V) || (cin.peek() != '\n' || !(V >= 2))) //проверка на корректность ввода
        {
            cin.clear();
            while (cin.get() != '\n');
            cout << "Введено недопустимое значение " << V << " Повторите попытку." << endl;
        }
        int **VES = new int*[V]; //массив временных меток
        for (int i = 0; i < V; i++)
            VES[i] = new int[V];
        int VV = V*V;
        int start = 0;;
        cout << "Заполните матрицу весов графа " << endl;      // Матрица весов графа
        cout << setw(4);
        for (int i = 0; i < V; i++)
            cout << "|x" << i + 1;
        cout << endl;
        for (int i = 0; i < V; i++)
        {
            cout << "X" << i + 1 << '|';
            for (int j = 0; j < V; j++)
                while (!(cin >> VES[i][j]) || !(VES[i][j] >= 0)) //проверка на корректность ввода
                {
                    cin.clear();
                    cout << "Введено недопустимое значение " << VES[i][j] << " Повторите ввод матрицы заново." << endl;
                }
        }
        //проверка пути
        bool put_b = true;
        int* put_mas = new int[V];
        int kk = 0;
        int put_count_iteration_2 = -1;
        int* put_temp_metka = new int[V*V];
        put_temp_metka[0] = -100;
        int pk = 1;
        put_temp_metka[pk] = V;
        put_b = put(put_b, pk, put_temp_metka, VES, V);
        if (put_b == true)
        {
            int t = 0;
            int p = 0;
            int *mas_use = new int[VV];
            int count_iteration_1 = -1;
            int temp_metka = start;
            int **total_min = new int*[VV]; //минимум в каждой итерации
            for (int i = 0; i < VV; i++)
                total_min[i] = new int[VV];
            for (int i = 0; i < VV; i++)
                total_min[i][p] = INT_MAX;
            int **massiv_temp_metok = new int*[VV]; //массив временных меток
            for (int i = 0; i < VV; i++)
                massiv_temp_metok[i] = new int[VV];
            int *mass_x = new int[V];
            int r = 0;
            for (int i = 1; i < V; i++)
                if (i != 0)
                {
                    mass_x[i - 1] = i;
                    r++;
                }
            cout << "Шаг 1. Т.к. d(s)=" << temp_metka << "*, то полагаем, d(x1)=0*, X=x1, d(x2)=...=d(x" << V << ")= inf" << endl;
            //////////////////////////
            bool put = false;
            if (VES[0][V] != 0)
                put = true;
            int **massiv_metok_for_output = new int*[V];
            for (int i = 0; i < V; i++)
                massiv_metok_for_output[i] = new int[VV];
            /////////////////////////
            while (temp_metka != V)
            {
                count_iteration_1++;
                cout << endl;
                int temp;
                int q = 0;
                int g = 0;
                int **min = new int*[1];
                for (int i = 0; i < V; i++)
                    min[i] = new int[V];
                int m_i = 0, m_j = 0;
                int *temp_x = new int[V];
                for (int i = 0; i < V; i++)
                    temp_x[i] = INT_MAX;
                int *temp_value = new int[V];
                int *temp_value_original = new int[V];
                int k = 0;
                cout << count_iteration_1 + 1 << " итерация" << endl;
                /////////////////////////////////////////////////////////
                cout << "Шаг 2. Множество вершин, непосредственно следующих за X=х" << temp_metka + 1 << " с временными метками" << endl;
                int *mass_x_temp = new int[r];
                int y = 0;
                for (int j = 0; j < V; j++)
                {
                    massiv_temp_metok[count_iteration_1][j] = VES[temp_metka][j];
                    massiv_metok_for_output[count_iteration_1][j] = VES[temp_metka][j];
                    if (VES[temp_metka][j] != 0)
                    {
                        bool flag = true;
                        for (int i = 0; i < t; i++)
                        {
                            if (mas_use[i] == j)
                            {
                                flag = false;
                                break;
                            }
                            else
                            {
                                flag = true;
                            }
                        }
                        if (flag == true)
                        {
                            temp_x[k] = j;
                            k++;
                        }
                        temp_value[k] = VES[temp_metka][j];
                        temp_value_original[j] = VES[count_iteration_1][j];
                    }
                }
                if (count_iteration_1 >= 1)
                {
                    int y = 0;
                    bool flag2 = false;
                    for (int i = 0; i < r; i++)
                    {
                        if (mass_x[i] != temp_metka)
                        {
                            mass_x_temp[y] = mass_x[i];
                            y++;
                        }
                    }
                    mass_x = &mass_x_temp[0];
                    r--;
                }
                cout << "S = {";
                for (int i = 0; i < k; i++)
                {
                    if (i < k - 1)
                        cout << "x" << temp_x[i] + 1 << ", ";
                    else
                        cout << "x" << temp_x[i] + 1;
                }
                cout << "}.Пересчитаем временные метки этих вершин: " << endl;
                if (count_iteration_1 == 0)
                {
                    for (int i = 0; i < k; i++)
                    {
                        int one = INT_MAX;
                        int two = temp_metka + temp_value[i + 1];
                        if (one < two)
                        {
                            min[q][g] = one;
                            for (int i = 0; i < V; i++)
                                if (massiv_temp_metok[count_iteration_1][i] == min[q][g])
                                {
                                    min[q][g + 1] = i;
                                }
                        }
                        else
                        {
                            min[q][g] = two;
                            for (int i = 0; i < V; i++)
                                if (massiv_temp_metok[count_iteration_1][i] == min[q][g])
                                {
                                    min[q][g + 1] = i;
                                }
                        }
                        cout << "d(x" << temp_x[i] + 1 << ") = min {" << "inf" << "," << 0 << "*+" << temp_value[i + 1] << "}= " << min[q][g] << endl;
                        q++;
                    }
                }
                else if (count_iteration_1 >= 1)
                {
                    for (int i = 0; i < k; i++)
                    {
                        int one = massiv_temp_metok[count_iteration_1 - 1][temp_x[i]];
                        if (massiv_temp_metok[count_iteration_1 - 1][temp_x[i]] == 0)
                            one = INT_MAX;
                        int two = total_min[count_iteration_1 - 1][p] + temp_value[i + 1];
                        if (one > two)
                        {
                            min[q][g] = two;
                        }
                        else if (one < two)
                        {
                            min[q][g] = one;
                        }
                        else if (one == two)
                            min[q][g] = one;
                        cout << "d(x" << temp_x[i] + 1 << ") = min {";
                        if (massiv_temp_metok[count_iteration_1 - 1][temp_x[i]] == INT_MAX)
                            cout << "inf";
                        else
                            cout << massiv_temp_metok[count_iteration_1 - 1][temp_x[i]];
                        cout << "," << total_min[count_iteration_1 - 1][p] << "*+" << temp_value[i + 1];
                        cout << "}=" << min[q][g] << endl;
                        q++;
                    }
                }
                /////////////////////////////////////////////////////////
                cout << "Шаг 3. min{";
                for (int i = 0; i < r; i++)
                {
                    if (i < r - 1)
                        cout << "x" << mass_x[i] + 1 << ", ";
                    else
                        cout << "x" << mass_x[i] + 1;
                }
                cout << "} = min{";
                if (count_iteration_1 >= 1)
                    for (int j = 0; j < V; j++)
                    {
                        massiv_temp_metok[count_iteration_1][j] = massiv_temp_metok[count_iteration_1 - 1][j];
                        //if(massiv_temp_metok[count_iteration_1 - 1][j] == INT_MAX)
                        massiv_metok_for_output[count_iteration_1][j] = massiv_metok_for_output[count_iteration_1 - 1][j];
                        //massiv_metok_for_output[count_iteration_1][j] = 999;
                    }
                for (int j = 0; j < V; j++)
                    if (massiv_temp_metok[count_iteration_1][j] == 0)
                        massiv_temp_metok[count_iteration_1][j] = INT_MAX;
                int temp_count = 0;
                for (int i = 0; i < V; i++)
                {
                    for (int a = 0; a < k; a++)
                    {
                        if (temp_x[a] == i)
                        {
                            temp_count++;
                            massiv_temp_metok[count_iteration_1][i] = min[temp_count - 1][g];
                            massiv_metok_for_output[count_iteration_1][i] = min[temp_count - 1][g];
                        }
                    }
                }
                for (int i = 0; i < r; i++)
                {
                    if (i < r - 1)
                    {
                        if (massiv_temp_metok[count_iteration_1][mass_x[i]] == INT_MAX)
                            cout << "inf" << ", ";
                        else
                            cout << massiv_temp_metok[count_iteration_1][mass_x[i]] << ", ";
                    }
                    else
                    {
                        if (massiv_temp_metok[count_iteration_1][mass_x[i]] == INT_MAX)
                            cout << "inf" << ", ";
                        else
                            cout << massiv_temp_metok[count_iteration_1][mass_x[i]];
                    }
                }
                int temp_int;
                for (int i = 0; i < V; i++)
                {
                    if (total_min[count_iteration_1][p] > massiv_temp_metok[count_iteration_1][i])
                    {
                        total_min[count_iteration_1][p] = massiv_temp_metok[count_iteration_1][i];
                        total_min[count_iteration_1][p + 1] = i;
                        temp = i + 1;
                        temp_int = i;
                    }
                }
                massiv_temp_metok[count_iteration_1][temp_int] = INT_MAX;
                cout << "}=" << total_min[count_iteration_1][p] << "*=x";
                mas_use[t] = temp - 1;
                t++;
                cout << temp << ", тогда X=x" << temp << endl;
                /////////////////////////////////////////////////////////
                if (temp != V)
                {
                    cout << "Шаг 4. т.к.х" << temp << "!=х" << V << ", то возвращаемся ко второму шагу." << endl;
                    temp_metka = temp - 1;
                }
                else
                {
                    cout << "Шаг 4. т.к.х" << temp << "=х" << V << " - КОНЕЦ АЛГОРИТМА" << endl;
                    temp_metka = V;
                }
            }
            cout << "Минимальный путь = " << total_min[count_iteration_1][p] << endl << endl;
            ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
            cout << "ЭТАП 2" << endl;
            int count_iteration_2 = -1;
            total_min[count_iteration_1 + 1][p + 1] = 0;
            total_min[count_iteration_1 + 1][p] = 0;
            int *total_min_step2 = new int[V];
            for (int i = 0; i < V; i++)
                total_min_step2[i] = INT_MAX;
            int h = 0;
            int *temp_result = new int[V*V];
            int *metka = new int[V];
            while (temp_metka != 1)
            {
                count_iteration_2++;
                cout << count_iteration_2 + 1 << " итерация" << endl;
                int *temp_x = new int[V];
                int k = 0;
                for (int j = 0; j < V; j++)
                {
                    if (VES[j][temp_metka - 1] != 0)
                    {
                        {
                            temp_x[k] = j;
                            k++;
                        }
                    }
                }
                cout << "Шаг 5. S={";
                int c;
                for (int i = 0; i < k; i++)
                {
                    c = temp_x[i];
                    if (i < k - 1)
                        cout << "x" << temp_x[i] + 1 << ", ";
                    else
                        cout << "x" << temp_x[i] + 1;
                }
                cout << "}" << endl;
                int index;
                int a = 0;
                int m = 0;
                /////////
                for (int i = 0; i < k; i++)
                {
                    for (int j = 0; j < V; j++)
                        if (total_min[j][p + 1] == temp_x[i])
                        {
                            //cout << "Делаю" << total_min[j][p] << "+" << VES[temp_x[i]][temp_metka - 1] << endl;
                            //cout << "Прошло сравнение " << total_min[j][p + 1] << " == " << temp_x[i] << "\n";
                            if (total_min[j][p] != INT_MAX)
                            {
                                temp_result[m] = total_min[j][p] + VES[temp_x[i]][temp_metka - 1];
                                if (total_min_step2[a] >= temp_result[m])
                                {
                                    total_min_step2[a] = temp_result[m];
                                    index = temp_x[i];
                                }
                                m++;
                            }
                        }
                }
                m = 0;
                for (int i = 0; i < k; i++)
                {
                    if (total_min_step2[a] != temp_result[m])
                        cout << "d(X)=" << total_min_step2[a] << "!=d(x";
                    else
                        cout << "d(X)=" << total_min_step2[a] << "=d(x";
                    cout << temp_x[i] + 1 << ")+w(x";
                    cout << temp_x[i] + 1 << ", x" << temp_metka << ")=";
                    for (int j = 0; j < V; j++)
                    {
                        if (total_min[j][p + 1] == temp_x[i])
                        {
                            if (total_min[j][p] != INT_MAX)
                                cout << total_min[j][p] << "+" << VES[temp_x[i]][temp_metka - 1] << "=" << temp_result[m] << endl;
                        }
                    }
                    m++;
                }
                a++;
                cout << "Включаем дугу(";
                for (int i = 0; i < k; i++)
                {
                    if (temp_x[i] == index)
                    {
                        cout << "x" << temp_x[i] + 1 << ",x" << temp_metka;
                        temp_metka = temp_x[i] + 1;
                    }
                }
                cout << ") в кратчайший путь Х = х" << temp_metka << "." << endl << endl;
                metka[h] = temp_metka;
                h++;
            }
            ////////////
            if (temp_metka == 1)
            {
                cout << "Шаг 6. Х=s=х" << temp_metka << ", завершение второго этапа." << endl << endl;
                cout << "Кратчайший путь от вершины х" << V << " построен.";
                cout << "Его длина(вес) равна " << total_min[count_iteration_1][p] << "." << endl;
                cout << "Cам путь образует следующая последовательность дуг: µ=";
                for (int i = h - 1; i >= 0; --i)
                    cout << "x" << metka[i] << "->";
                cout << "x" << V << endl;
            }
            cout << "\t\tМассив временных меток" << endl;
            for (int i = 0; i < V; i++)
            {
                if (i == 0)
                    cout << 0 << "\t";
                else
                    cout << "inf\t";
            }
            cout << endl;
            int metk;
            int cc = 0;
            int *col = new int[V];
            int c_col = 0;
            for (int i = 0; i <= count_iteration_1; i++)
            {
                bool met = false;
                bool stroka = false;
                for (int j = 0; j < V; j++)
                {
                    if (massiv_metok_for_output[i][j] == total_min[cc][0] && col[c_col - 1] != j)
                    {
                        if (stroka == false)
                        {
                            cc++;
                            met = true;
                        }
                    }
                    if (met == true && stroka == false)
                    {
                        stroka = true;
                        if (j == 0)
                            cout << "0*\t";
                        else
                        {
                            if (massiv_metok_for_output[i][j] == 0)
                                cout << "inf\t";
                            else
                            {
                                if (col[c_col - 1] == j)
                                {
                                    cout << massiv_metok_for_output[i][j] << "\t";
                                }
                                else
                                    cout << massiv_metok_for_output[i][j] << "*\t";
                                col[c_col] = j;
                                c_col++;
                            }
                        }
                    }
                    else
                    {
                        if (j == 0)
                            cout << "0\t";
                        else
                        {
                            if (massiv_metok_for_output[i][j] == 0)
                                cout << "inf\t";
                            else
                                cout << massiv_metok_for_output[i][j] << "\t";
                        }
                    }
                }
                cout << endl;
            }
        }
        ///////////////////////
        system("pause");
    }

}