#include <iostream>
#include <conio.h>
#include <windows.h>
#include <iomanip>
using namespace std;
char NEWT[256];
int v;
HANDLE out = GetStdHandle(STD_OUTPUT_HANDLE);
int main()
{
	srand(time(0));
	setlocale(0, "Russian");
	int i, j;
	int infinity = 100;// Бесконечность
	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 = 10;
	int p;
	p = VERTEX;//Число вершин в графе
	for (int i = 0; i < VERTEX; i++)
	{
		VES[i][i] = 0;
		for (int j = i + 1; j < VERTEX; j++) {
			VES[i][j] = rand() % 100;
			VES[j][i] = VES[i][j];
		}
	}

	/*Вывод матрицы*/
	//VES[3][0] = infinity;
	//VES[4][0] = infinity;

	cout << setw(20) << "Матрица расстояний:";
	cout << "" << endl;
	cout << endl;
	cout << "   |  1|  2|  3|  4|  5|  6|  7|  8|  9| 10|" << endl;
	cout << setw(20) << "--------------------------------------------" << endl;
	for (int i = 0; i<VERTEX; i++)
	{
		cout << setw(1) << "";
		cout << setw(2) << i + 1 << "|";
		for (int j = 0; j < VERTEX; j++)
		{

			cout << setw(3) << VES[i][j];
			cout << setw(1) << "|";

		}
		cout << endl;
		cout << setw(20) << "--------------------------------------------" << endl;
	}
	//VES[3][0] = infinity;
	//VES[4][0] = infinity;


	//
	// Будем искать путь из вершины s в вершину g по циклу
	int start;// Номер исходной вершины
	int end;// Номер конечной вершины
	cout << endl;
N: cout << "Начальная вершина: "; // Номер может изменяться от 0 до p-1
	cin >> start;
	cout << endl;
	if (start>(p - 1) && start<0)
	{
		cout << "Нет такой вершины повторите ввод..." << endl; goto N; // на случай неверных данных
	}
	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 << "Кратчайший путь из вершины";
					cout << " "<< start + 1;
					cout << " в вершину ";
					cout << end + 1;
					cout << ":";
					u = end;
					while (u != start)
					{
						cout << " " << u + 1;
						u = PredVertex[u];
					}
					cout << " " << start + 1 << ". ";
					cout << "Длина пути - ";
					cout << DlinaPuti[end];
					cout << endl;
					break;
				}
				x[v] = 1;
			}
		}	cout << endl;

	}
	cout << endl;
	system("pause");
	return 0;
}