Найти алгоритмом Дейкстры кратчайший путь между двумя заданными вершинами - C++ - Ответ 15433669

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
using namespace std ;
 
int SIZE;
int main()
{
 
    setlocale(LC_ALL, "RUSSIAN");
    //Создаем файловый поток и связываем его с файлом
    ifstream in("input.txt");
    if (in.is_open()){
        //Если открытие файла прошло успешно
        //Вначале посчитаем сколько чисел в файле
        int count = 0;// число чисел в файле
        int temp1;//Временная переменная
 
        while (!in.eof())// пробегаем пока не встретим конец файла eof
        {
            in >> temp1;//в пустоту считываем из файла числа
            count++;// увеличиваем счетчик числа чисел
        }
 
        //Число чисел посчитано, теперь нам нужно понять сколько
        //чисел в одной строке
        //Для этого посчитаем число пробелов до знака перевода на новую строку
 
        //Вначале переведем каретку в потоке в начало файла
        in.seekg(0, ios::beg);
        in.clear();
 
        //Число пробелов в первой строчке вначале равно 0
        int count_space = 0;
        char symbol;
 
        while (!in.eof())//на всякий случай цикл ограничиваем концом файла
        {
        //теперь нам нужно считывать не числа, а посимвольно считывать данные
        in.get(symbol);//считали текущий символ
        if (symbol == ' ') count_space++;//Если это пробел, то число пробелов увеличиваем
        if (symbol == '\n') break;//Если дошли до конца строки, то выходим из цикла
        }
        //cout << count_space << endl;
 
        //Опять переходим в потоке в начало файла
        in.seekg(0, ios::beg);
        in.clear();
 
        //Теперь мы знаем сколько чисел в файле и сколько пробелов в первой строке.
        //Теперь можем считать матрицу.
 
        SIZE = count / (count_space + 1);//число строк
 
    int a[SIZE][SIZE]; // матрица связей
    int d[SIZE]; // минимальное расстояние
    int v[SIZE]; // посещенные вершины
    int temp, minindex, min;
    int begin_index = 0;
    system("chcp 1251");
    system("cls");
//    // Инициализация матрицы связей
//    for (int i = 0; i<SIZE; i++){
//        a[i][i] = 0;
//        for (int j = i + 1; j<SIZE; j++) {
//            printf("Введите расстояние %d - %d: ", i + 1, j + 1);
//            scanf("%d", &temp);
//            a[i][j] = temp;
//            a[j][i] = temp;
//        }
//    }
//    // Вывод матрицы связей
//    for (int i = 0; i<SIZE; i++){
//        for (int j = 0; j<SIZE; j++)
//            printf("%5d ", a[i][j]);
//            printf("\n");
//    }
 
    for (int i=0; i < SIZE; i++){
        for (int j=0; j<SIZE; j++){
            in >> a[i][j];
        };
    };
    for (int i=0; i < SIZE; i++){
        for (int j=0; j<SIZE; j++){
            cout << a[i][j] << '\t';
        };
    cout << endl;
    };
 
    //Инициализация вершин и расстояний
    for (int i = 0; i<SIZE; i++){
        d[i] = 10000;
        v[i] = 1;
    }
    d[begin_index] = 0;
    // Шаг алгоритма
    do {
        minindex = 10000;
        min = 10000;
        for (int i = 0; i<SIZE; i++){ // Если вершину ещё не обошли и вес меньше min
            if ((v[i] == 1) && (d[i]<min)){ // Переприсваиваем значения
                min = d[i];
                minindex = i;
            }
        }
        // Добавляем найденный минимальный вес
        // к текущему весу вершины
        // и сравниваем с текущим минимальным весом вершины
        if (minindex != 10000){
            for (int i = 0; i<SIZE; i++){
                if (a[minindex][i] > 0){
                    temp = min + a[minindex][i];
                    if (temp < d[i]){
                        d[i] = temp;
                    }
                }
            }
            v[minindex] = 0;
        }
    }
    while (minindex < 10000);
    // Вывод кратчайших расстояний до вершин
    printf("\nКратчайшие расстояния до вершин: \n");
        for (int i = 0; i<SIZE; i++)
            printf("%5d ", d[i]);
 
    // Восстановление пути
    int ver[SIZE]; // массив посещенных вершин
    int end = 4; // индекс конечной вершины = 5 - 1
    ver[0] = end + 1; // начальный элемент - конечная вершина
    int k = 1; // индекс предыдущей вершины
    int weight = d[end]; // вес конечной вершины
 
    while (end != begin_index) // пока не дошли до начальной вершины
    {
        for (int i = 0; i<SIZE; i++) // просматриваем все вершины
            if (a[i][end] != 0)   // если связь есть
            {
            int temp = weight - a[i][end]; // определяем вес пути из предыдущей вершины
                if (temp == d[i]) // если вес совпал с рассчитанным
                {                 // значит из этой вершины и был переход
                    weight = temp; // сохраняем новый вес
                    end = i;       // сохраняем предыдущую вершину
                    ver[k] = i + 1; // и записываем ее в массив
                    k++;
                }
            }
    }
    // Вывод пути (начальная вершина оказалась в конце массива из k элементов)
    printf("\nВывод кратчайшего пути\n");
        for (int i = k - 1; i >= 0; i--)
            printf("%3d ", ver[i]);
            getchar(); getchar();
    }
    else{
        cout << "Error!";
    }
    return 0;
}