Алгоритм Дейкстры - нахождение кратчайшего маршрута до каждой вершины

#include <fstream>
 
typedef unsigned short ushort;
 
/*template <class T>
void printArray(T *arr, int N);
 
*/
int main()
{
    std::ifstream fin("input.txt");
    std::ofstream fout;
    ushort *marks = NULL; // массив маркировок вершин графа
    ushort *permanentMarks = NULL; // массив наличия постоянной марки
    short **adjacencyMatrix = NULL; // матрица смежности
    short p; // число вершин графа
    short S; // номер вершины отправления
    short curS; // текущая вершина
    short F; // номер вершины завершения пути
 
    fin >> p >> S >> F;
    --S;
    --F;
    // выделение памяти  и инициализация матрицы смежности графа
    marks = new ushort[p];
    permanentMarks = new ushort[p];
    memset(marks, 0xFF, sizeof (*marks) * p);
    memset(permanentMarks, 0, sizeof (*permanentMarks) * p);
    adjacencyMatrix = new short*[p];
    for (int i = 0; i < p; ++i)
    {
        adjacencyMatrix[i] = new short[p];
        for (int j = 0; j < p; ++j)
            fin >> adjacencyMatrix[i][j];
    }
    fin.close();
 
    permanentMarks[S] = 1;
    marks[S] = 0;
    curS = S;
    while (!permanentMarks[F]) // пока не помечен конец пути
    {
        for (int j = 0; j < p; ++j)
        {
            if (adjacencyMatrix[curS][j] != -1 && !permanentMarks[j]
                && (marks[curS] + adjacencyMatrix[curS][j]) < marks[j])
            {
                marks[j] = marks[curS] + adjacencyMatrix[curS][j];
            }
        }
        // поиск минимальной непомеченной метки
 
        /* вначале ищем любую непомеченную вершину */
        for (int i = 0; i < p; ++i)
        {
            if (!permanentMarks[i])
            {
                curS = i;
                break;
            }
        }
        for (int i = curS + 1; i < p; ++i)
        {
            if (!permanentMarks[i] && marks[i] < marks[curS])
                curS = i;
        }
        permanentMarks[curS] = 1;
        /*
        std::cout << "Marks:\n";
        printArray(marks, p);
        std::cout << "-----------------\n";
        std::cout << "PermanentMarks:\n";
        printArray(permanentMarks, p);
        std::cout << "*******************\n";*/
    }
 
    /*std::cout << marks[F];*/
    fout.open("output.txt");
    if (marks[F] == USHRT_MAX)
        fout << -1;
    else
        fout << marks[F];
    fout.close();
 
    delete[] marks;
    delete[] permanentMarks;
    for (int i = p -1; i >= 0; --i)
        delete[] adjacencyMatrix[i];
    delete[] adjacencyMatrix;
 
    return 0;
}
/*
template <class T>
void printArray(T *arr, int N)
{
    for (int i = 0; i < N; ++i)
    {
        std::cout << std::setw(6) << i << ' ';
    }
    std::cout << std::endl;
    for (int i = 0; i < N; ++i)
    {
        std::cout << std::setw(6) << arr[i] << ' ';
    }
    std::cout << std::endl;
}*/

#include <fstream>
#include <iostream>
#include <iomanip>
#include <climits>
#include <cstring>
#include <list>
 
typedef unsigned short ushort;
 
int getIndexOfVertexWithMinimalDistance(const short * adjancedRow,
                                        const int vertices,
                                        const ushort * marks);
template <class T>
void printArray(T *arr, int N);
 
int main()
{
    std::ifstream fin("input.txt");
    std::ofstream fout;
    ushort *marks = NULL; // массив маркировок вершин графа
    ushort *permanentMarks = NULL; // массив наличия постоянной марки
    short **adjacencyMatrix = NULL; // матрица смежности
    short verticesNum; // число вершин графа
    short startVertexIndex; // номер вершины отправления
    short curVertexIndex; // текущая вершина
    short endVertexIndex; // номер вершины завершения пути
    std::list<int> shortestPath;
 
    fin >> verticesNum >> startVertexIndex >> endVertexIndex;
    --startVertexIndex;
    --endVertexIndex;
    // выделение памяти  и инициализация матрицы смежности графа
    marks = new ushort[verticesNum];
    permanentMarks = new ushort[verticesNum];
    memset(marks, 0xFF, sizeof (*marks) * verticesNum);
    memset(permanentMarks, 0, sizeof (*permanentMarks) * verticesNum);
    adjacencyMatrix = new short*[verticesNum];
    for (int i = 0; i < verticesNum; ++i)
    {
        adjacencyMatrix[i] = new short[verticesNum];
        for (int j = 0; j < verticesNum; ++j)
        {
            int val;
 
            fin >> val;
            if (val == 0)
            {
                val = -1;
            }
 
            adjacencyMatrix[i][j] = val;
        }
    }
    fin.close();
 
    permanentMarks[startVertexIndex] = 1;
    marks[startVertexIndex] = 0;
    curVertexIndex = startVertexIndex;
    while (!permanentMarks[endVertexIndex]) // пока не помечен конец пути
    {
        for (int j = 0; j < verticesNum; ++j)
        {
            if (adjacencyMatrix[curVertexIndex][j] != -1 && !permanentMarks[j]
                && (marks[curVertexIndex] + adjacencyMatrix[curVertexIndex][j]) < marks[j])
            {
                marks[j] = marks[curVertexIndex] + adjacencyMatrix[curVertexIndex][j];
            }
        }
        // поиск минимальной непомеченной метки
 
        /* вначале ищем любую непомеченную вершину */
        for (int i = 0; i < verticesNum; ++i)
        {
            if (!permanentMarks[i])
            {
                curVertexIndex = i;
                break;
            }
        }
        for (int i = curVertexIndex + 1; i < verticesNum; ++i)
        {
            if (!permanentMarks[i] && marks[i] < marks[curVertexIndex])
                curVertexIndex = i;
        }
        permanentMarks[curVertexIndex] = 1;
        /*
        std::cout << "Marks:\n";
        printArray(marks, p);
        std::cout << "-----------------\n";
        std::cout << "PermanentMarks:\n";
        printArray(permanentMarks, p);
        std::cout << "*******************\n";*/
    }
 
    /*std::cout << marks[F];*/
    fout.open("output.txt");
    if (marks[endVertexIndex] == USHRT_MAX)
    {
        fout << -1;
    }
    else
    {
        fout << marks[endVertexIndex] << std::endl;
 
        std::cout << "Marks:\n";
        printArray(marks, verticesNum);
        std::cout << "-----------------\n";
        std::cout << "PermanentMarks:\n";
        printArray(permanentMarks, verticesNum);
        std::cout << "*******************\n";
 
 
        curVertexIndex = endVertexIndex;
        shortestPath.push_front(curVertexIndex + 1);
 
        while (curVertexIndex != startVertexIndex)
        {
            std::cout << "currentRow:\n";
            printArray(adjacencyMatrix[curVertexIndex], verticesNum);
            std::cout << "****************" << std::endl;
 
            curVertexIndex =
               getIndexOfVertexWithMinimalDistance(adjacencyMatrix[curVertexIndex],
                                                   verticesNum,
                                                   marks);
 
            shortestPath.push_front(curVertexIndex + 1);
        }
 
        for (std::list<int>::iterator it = shortestPath.begin();
             it != shortestPath.end(); ++it)
        {
            fout << *it << " -> ";
        }
    }
    fout.close();
 
    delete[] marks;
    delete[] permanentMarks;
    for (int i = verticesNum -1; i >= 0; --i)
    {
        delete[] adjacencyMatrix[i];
    }
    delete[] adjacencyMatrix;
 
    return 0;
}
 
int getIndexOfVertexWithMinimalDistance(const short * adjancedRow,
                                        const int vertices,
                                        const ushort * marks)
{
    int minIndex;
 
    // поиск индекса первого положительного числа
    for (minIndex = 0; adjancedRow[minIndex] <= 0; ++minIndex);
    // поиск индекса минимального положительного числа
    for (int i = 1; i < vertices; ++i)
    {
        if (adjancedRow[i] < adjancedRow[minIndex] && adjancedRow[i] > 0 &&
                marks[i] < marks[minIndex])
        {
            minIndex = i;
        }
    }
 
    return minIndex;
}
 
template <class T>
void printArray(T *arr, int N)
{
    for (int i = 0; i < N; ++i)
    {
        std::cout << std::setw(6) << i << ' ';
    }
    std::cout << std::endl;
    for (int i = 0; i < N; ++i)
    {
        std::cout << std::setw(6) << arr[i] << ' ';
    }
    std::cout << std::endl;
}

#include <fstream>
#include <iostream>
#include <iomanip>
#include <climits>
#include <cstring>
#include <list>
 
typedef unsigned short ushort;
 
int getIndexOfVertexWithMinimalDistance(const short * adjancedRow,
                                        const int vertices,
                                        const ushort * marks,
                                        int curVertexIndex);
template <class T>
void printArray(T *arr, int N);
 
int main()
{
    std::ifstream fin("input.txt");
    std::ofstream fout;
    ushort *marks = NULL; // массив маркировок вершин графа
    ushort *permanentMarks = NULL; // массив наличия постоянной марки
    short **adjacencyMatrix = NULL; // матрица смежности
    short verticesNum; // число вершин графа
    short startVertexIndex; // номер вершины отправления
    short curVertexIndex; // текущая вершина
    short endVertexIndex; // номер вершины завершения пути
    std::list<int> shortestPath;
 
    fin >> verticesNum >> startVertexIndex >> endVertexIndex;
    --startVertexIndex;
    --endVertexIndex;
    // выделение памяти  и инициализация матрицы смежности графа
    marks = new ushort[verticesNum];
    permanentMarks = new ushort[verticesNum];
    memset(marks, 0xFF, sizeof (*marks) * verticesNum);
    memset(permanentMarks, 0, sizeof (*permanentMarks) * verticesNum);
    adjacencyMatrix = new short*[verticesNum];
    for (int i = 0; i < verticesNum; ++i)
    {
        adjacencyMatrix[i] = new short[verticesNum];
        for (int j = 0; j < verticesNum; ++j)
        {
            int val;
 
            fin >> val;
            if (val == 0)
            {
                val = -1;
            }
 
            adjacencyMatrix[i][j] = val;
        }
    }
    fin.close();
 
    permanentMarks[startVertexIndex] = 1;
    marks[startVertexIndex] = 0;
    curVertexIndex = startVertexIndex;
    while (!permanentMarks[endVertexIndex]) // пока не помечен конец пути
    {
        for (int j = 0; j < verticesNum; ++j)
        {
            if (adjacencyMatrix[curVertexIndex][j] != -1 && !permanentMarks[j]
                && (marks[curVertexIndex] + adjacencyMatrix[curVertexIndex][j]) < marks[j])
            {
                marks[j] = marks[curVertexIndex] + adjacencyMatrix[curVertexIndex][j];
            }
        }
        // поиск минимальной непомеченной метки
 
        /* вначале ищем любую непомеченную вершину */
        for (int i = 0; i < verticesNum; ++i)
        {
            if (!permanentMarks[i])
            {
                curVertexIndex = i;
                break;
            }
        }
        for (int i = curVertexIndex + 1; i < verticesNum; ++i)
        {
            if (!permanentMarks[i] && marks[i] < marks[curVertexIndex])
                curVertexIndex = i;
        }
        permanentMarks[curVertexIndex] = 1;
        /*
        std::cout << "Marks:\n";
        printArray(marks, p);
        std::cout << "-----------------\n";
        std::cout << "PermanentMarks:\n";
        printArray(permanentMarks, p);
        std::cout << "*******************\n";*/
    }
 
    /*std::cout << marks[F];*/
    fout.open("output.txt");
    if (marks[endVertexIndex] == USHRT_MAX)
    {
        fout << -1;
    }
    else
    {
        fout << marks[endVertexIndex] << std::endl;
 
        std::cout << "Marks:\n";
        printArray(marks, verticesNum);
        std::cout << "-----------------\n";
//        std::cout << "PermanentMarks:\n";
//        printArray(permanentMarks, verticesNum);
//        std::cout << "*******************\n";
 
 
        curVertexIndex = endVertexIndex;
        shortestPath.push_front(curVertexIndex + 1);
 
        while (curVertexIndex != startVertexIndex)
        {
            std::cout << "currentRow:\n";
            printArray(adjacencyMatrix[curVertexIndex], verticesNum);
            std::cout << "****************" << std::endl;
 
            curVertexIndex =
               getIndexOfVertexWithMinimalDistance(adjacencyMatrix[curVertexIndex],
                                                   verticesNum,
                                                   marks,
                                                   curVertexIndex);
 
            shortestPath.push_front(curVertexIndex + 1);
        }
 
        for (std::list<int>::iterator it = shortestPath.begin();
             it != shortestPath.end(); ++it)
        {
            fout << *it << " -> ";
        }
    }
    fout.close();
 
    delete[] marks;
    delete[] permanentMarks;
    for (int i = verticesNum -1; i >= 0; --i)
    {
        delete[] adjacencyMatrix[i];
    }
    delete[] adjacencyMatrix;
 
    return 0;
}
 
int getIndexOfVertexWithMinimalDistance(const short * adjancedRow,
                                        const int vertices,
                                        const ushort * marks,
                                        int curVertexIndex)
{
    short curDistance = marks[curVertexIndex];
 
    // поиск индекса минимального положительного числа
    for (int i = 0; i < vertices; ++i)
    {
        if (adjancedRow[i] > 0 && (marks[i] + adjancedRow[i] == curDistance))
        {
            return i;
        }
    }
 
    return -1;
}
 
template <class T>
void printArray(T *arr, int N)
{
    for (int i = 0; i < N; ++i)
    {
        std::cout << std::setw(6) << i << ' ';
    }
    std::cout << std::endl;
    for (int i = 0; i < N; ++i)
    {
        std::cout << std::setw(6) << arr[i] << ' ';
    }
    std::cout << std::endl;
}