#include <iostream>

using namespace std;

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

// определение структуры для элемента стека
struct cell
{
    int value; // значение в элемента
    struct cell* next; // указатель на следующий элемент
};

// определение имени list для типа cell
typedef struct cell list;

// функция создания списка
list* modStack(int val)
{
    list* newStack; // создание указателя на новый список
    newStack = new list; // выделение памяти под новый список
    newStack->value = val; // запись в ячейку значения элемента списка
    newStack->next = NULL; // запись в ячейку указателя NULL на следующий элемент
    return(newStack);
}

// функция вывода содержимого стека на экран
void outputScreen(list* myStack)
{
    int pos = 0; // индекс позиции элемента в стеке
    list* tmp = myStack; // указатель на стек
    if (tmp == NULL)
    {
        std::cout << " ";
    }
    else
    {
        std::cout << "\n";
        do
        {
            pos++; // увеличение индекса позиции на 1
            std::cout << "-[" << pos << "]" << "(" << tmp->value << ")-"; // форматированный вывод элементов стека
            tmp = tmp->next; //присвоение tmp указателя на следующий элемент стека
        } while (tmp != NULL);
    }
    return;
}


// функция очистки стека
void clearList(list** myStack)
{
    list* tmp = *myStack; // указатель на первый элемент стека
    list* tmpNext = NULL; // указатель на следующий элемент стека
    if (tmp == NULL)
    {
        std::cout << "Невозможно очистить пустой или не созданный стек\n";
    }
    else
    {
        do
        {
            tmpNext = tmp->next; // присвоение указателя на следующий элемент
            delete tmp; // удаление указателя на текущий элемент
            tmp = tmpNext; // присвоение текущему указателю указателя на следующий элемент
        } while (tmp != NULL);
        *myStack = NULL; // обнуление указателя на стек
        //std::cout << "Стек успешно очищен\n";
    }

    return;
}



// функция извлечения элемента стека на заданной позиции
int PopStack(list** myStack)
{
    int val = 0;
    list* tmp = *myStack; // указатель на первый элемент стека
    list* tmpPrev = NULL; // указатель на предыдущий элемент стека

    if (tmp == NULL) // указатель на первый элемент стека NULL
    {
        std::cout << "Невозможно извлечь элемент из пустого или не созданного стека\n";
    }
    else
    {
        if (tmp->next == NULL) // указатель на следующий элемент NULL
        {
            val = tmp->value;
            clearList(myStack); // удаление всего стека из 1 элемента
        }
        else
        {
            do
            {
                tmpPrev = tmp; // присвоение указателю на предыдущий элемент указателя на текущий элемент
                tmp = tmp->next; // присвоение указателю на текущий элемент указателя на следующий элемент
            } while (tmp->next != NULL);
            val = tmp->value;

            tmpPrev->next = NULL; // указателю на следующий элемент для i-1 элемента присвоить указатель NULL
            delete tmp; // удаление указателя на извлеченный элемент
        }
    }
    return val;
}

// функция добавления элемента в стек
void PushStack(list** myStack, int val)
{
    list* tmp = *myStack; // указатель на первый элемент стека
    list* tmpPrev = NULL; // указатель на предыдущий элемент стека


    if (tmp == NULL)
    {
        *myStack = modStack(val); // создание стека с текущим элементом
        //std::cout << "Новый стек успешно создан\n";
    }
    else
    {
        do
        {
            tmpPrev = tmp; // присвоение указателю на предыдущий элемент указателя на текущий элемент
            tmp = tmp->next; // присвоение указателю на текущий элемент указателя на следующий элемент
        } while (tmp != NULL); // указатель на текущий элемент NULL

        tmpPrev->next = modStack(val); // присвоение указателю предыдущего элемента на следующий элемент указателя на введенный элемент
    }

    //std::cout << "Новый элемент со значением " << val << " добавлен в конец стека\n";
    return;
}


// функция топологической сортировки графа
void topological_s(int(*matrix)[n], int inf, list** next, int** sorted)
{

    int i, j, k; // индексные переменные
    int u = 0; // номер рассматриваемой вершины
    int in_degree[n] = { 0 }; // массив входящих степеней вершин

    // заполнение массива входящих степеней вершин
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (matrix[i][j] != inf)
            {
                in_degree[j]++;
            }
        }
    }

    for (i = 0; i < n; i++)
    {
        if (in_degree[i] == 0)
        {
            PushStack(next, i);
        }
    }

    k = 0;
    // пока существую вершины с входящей степенью 0
    while (*next != NULL)
    {
        u = PopStack(next); // выбор вершины для обработки из начала списка next
        (*sorted)[k++] = u; // запись вершины u в список sorted

        // поиск вершин с входящей степенью 0 после ослабления графа
        for (i = 0; i < n; i++)
        {
            if (matrix[u][i] != inf)
            {
                in_degree[i]--;
                if (in_degree[i] == 0)
                {
                    PushStack(next, i);
                }
            }
        }

    }
    return;
}


// поиск кратчайших путей
int* dag_shortest_path(int(*matrix)[n], int s, int inf, int* sorted)
{
    int* shortest = new int[n]; // массив весов кратчайших путей
    int* pred = new int[n]; // массив предыдущих вершин
    int i, j, k; // индексные переменные

    // инициализация массива shortest и pred
    for (i = 0; i < n; i++)
    {
        pred[i] = -1;
        if (i != s) shortest[i] = inf;
        else shortest[i] = 0;
    }

    // вычисление кратчайших путей из заданной вершины s
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (matrix[sorted[i]][j] != inf) // если путь существует
            {
                if ((shortest[sorted[i]] + matrix[sorted[i]][j]) < shortest[j]) // новый вес пути меньше текущего
                {
                    shortest[j] = shortest[sorted[i]] + matrix[sorted[i]][j]; // присвоить новый вес кратчайшего пути
                    pred[j] = sorted[i];
                }
            }
        }

    }
    return shortest;
}

int main()
{
    setlocale(LC_ALL, "RUS");

    int s = 0; // вершина для поиска критического пути
    int inf = 10000; // бесконечно большая величина
    int* shrt; // указатель на массив кратчайших путей
    int i = 0; // счетчик
    int* sorted = new int[n] { 0 };
    list* next = NULL;


    int matrix[][n] =
    {
    { inf, 3, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf },
    { inf, inf, 4, inf, inf, inf, inf, inf, inf, inf, inf, inf },
    { inf, inf, inf, 15, 6, inf, inf, inf, inf, inf, inf, inf },
    { inf, inf, inf, inf, inf, 34, inf, inf, inf, inf, inf, inf },
    { inf, inf, inf, inf, inf, 9, inf, inf, inf, inf, inf, inf },
    { inf, inf, inf, inf, inf, inf, 8, inf, inf, inf, inf, inf },
    { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, 19, inf },
    { inf, inf, inf, inf, inf, inf, inf, inf, 12, inf, inf, inf },
    { inf, inf, inf, inf, 11, inf, inf, inf, inf, inf, inf, inf },
    { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, 11, inf },
    { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, 10 },
    { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf }
    };

    cout << "Введите начальную вершину " << endl;
    cin >> s; // исходная вершина

    topological_s(matrix, inf, &next, &sorted);

    // форматированный вывод массива, возвращаемого топологической сортировкой
    cout << "\n\nЛинейный список вершин графа возвращаемый топологической сортировкой: "<<endl;
    for (i = 0; i < n; i++)
    {
        cout << sorted[i] << " ";
    }

    shrt = dag_shortest_path(matrix, s, inf, sorted);// массив кратчайших путей из вершины s

    cout << "\n\nСписок кратчайших путей из вершины " << s << " :" << endl;

    // форматированный вывод массива кратчайших путей
    for (i = 0; i < n; i++)
    {
        if (shrt[i] == inf)
        {
            cout << "(" << s << ", " << i << ") не существует  " << endl;
        }
        else
        {
            cout << "(" << s << ", " << i << ") = " << shrt[i] << endl;
        }
    }
    cout << endl;

    system("pause");

}