Переписать код с использование функций - C++ - Ответ 3914129

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <windows.h>
#include<iomanip>
 
using namespace std;
 
char NEWT[256];
int v;
 
int main()
{   setlocale(LC_ALL, "Russian");
int i,j;
bool f=true;
int infinity=10000;  // Бесконечность
int VES[100][100];   // Матрица весов графа
int x[100];          //Массив, содержащий единицы и нули для каждой вершины,
// x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
// x[i]=1 - кратчайший путь в i-ю вершину уже найден
 
int DlinaPuti[100];     //t[i] - длина кратчайшего пути от вершины s в i
int PredVertex[100];    //h[i] - вершина, предшествующая i-й вершине на кратчайшем пути
int VERTEX;
int p;                         
cout<<("Ввести количество вершин в графе ")<<endl;
cin>>VERTEX;
p= VERTEX;           //Число вершин в графе
cout<<("Заполните матрицу весов графа ")<<endl;      // Матрица весов графа
cout<<setw(4);
int k = 0;
for (i=0;i<VERTEX;i++)
{
    cout<<("|x")<<i+1;
    k++;
}
cout<<endl;
 
for(i=0;i<VERTEX;i++)
{
    cout<<("X")<<i+1<<'|';
    for(j=0;j<VERTEX;j++)
    {
        cin>>VES[i][j];
    }
}
// Будем искать путь из вершины s в вершину g по циклу
int start;    // Номер исходной вершины
int end;      // Номер конечной вершины
while (f)
{
    cout<<("Введите стартовую вершину: " );   // Номер может изменяться от 0 до p-1
    cin>>start;
    if (start < k && start > 0)
    {
        start=start-1;   //так как массив начинается с 0 отнимаем от вводимой цифры 1
        for (int prosto=0;prosto<VERTEX;prosto++)
        {
            end=prosto;         //цикл прогоняет алгоритм Флойда p-ое количество раз преврашая его в алгоритм Дейкстры  
            if (end==start)
            {
                continue;   //исключаем просчет растояния между одной и той же точкой
            }
            else
            {// Инициализируем начальные значения массивов
                int u;   // Счетчик вершин
                for (u=0;u<p;u++)
                {
                    DlinaPuti[u]=infinity;    //Сначала все кратчайшие пути из s в i равны бесконечности
                    x[u]=0;                  // и нет кратчайшего пути ни для одной вершины
                }
                PredVertex[start]=0;  // s - начало пути, поэтому этой вершине ничего не предшествует
                DlinaPuti[start]=0;   // Кратчайший путь из s в s равен 0
                x[start]=1;           // Для вершины s найден кратчайший путь
                v=start;              // Делаем s текущей вершиной
 
                while(1)
                {
                    // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
                    for(u=0;u<p;u++)
                    {
                        if(VES[v][u]==0)
                            {
                                continue; // Вершины u и v несмежные
                            }
                        if(x[u]==0 && DlinaPuti[u]>DlinaPuti[v]+VES[v][u]) //Если для вершины 'u' еще не 
                            //найден кратчайший путь
                            // и новый путь в 'u' короче чем 
                            //старый, то
                        {
                            DlinaPuti[u]=DlinaPuti[v]+VES[v][u];  //запоминаем более короткую длину пути в массив t[и]
                            PredVertex[u]=v;   //запоминаем, что v->u часть кратчайшего пути из s->u
                        }
                    }
 
                    // Ищем из всех длин некратчайших путей самый короткий
                    int w=infinity;                   // Для поиска самого короткого пути
                    v=-1;                             // В конце поиска v - вершина, в которую будет 
                    // найден новый кратчайший путь. Она станет 
                    // текущей вершиной
                    for(u=0;u<p;u++)                  // Перебираем все вершины.
                    {
                        if(x[u]==0 && DlinaPuti[u]<w)           // Если для вершины не найден кратчайший 
                            // путь и если длина пути в вершину 'u' меньше
                            // уже найденной, то
                        {
                            v=u;                         // текущей вершиной становится 'u'-я вершина
                            w= DlinaPuti[u];
                        }
                    }
                    if(v==-1)
                    {
                        cout<<("Нет пути из вершины ")<<start+1;
                        cout<<(" в вершину ")<<end+1<<"."<<endl;
                        break;
                    }
                    if(v==end) // Найден кратчайший путь,
                    {   // выводим его
                        cout<<("Кратчайший путь из вершины ")<<start+1;
                        cout<<(" в вершину ")<<end+1<<":";
                        u=end;
                        while(u!=start)
                        {
                            cout<<" "<<u+1;
                            u=PredVertex[u];
                        }
                        cout<<" "<<start+1<<(". Длина пути - ")<< DlinaPuti[end];
                        cout<<endl;
                        break;
                    }
                    x[v]=1;
                    f = false;
                }
       }
} 
    }
    else
    {
        cout << "Нет такой вершины повторите ввод..."<<endl;
    }
}
 
return 0;
}