#include <iostream>
#include <iomanip>
//#include <windows.h>
using namespace std;
//Функция проверки, можно ли перейти в данный узел
bool check(int key, int *mas, int kol) {
for (int j = 0; j < kol; j++)
if (mas[j] == key) //Если переход в этот узел уже был
return false;
return true;
}
int main() {
// SetConsoleCP(1251);
// SetConsoleOutputCP(1251);
int kol;
do //Ввод кол-ва узлов сети
{
cout << "Введите количество узлов(2-10) --> ";
cin >> kol;
} while (kol < 2 || kol > 10);
//Создание матрицы смежности
int **arr = new int *[kol];
for (int i = 0; i < kol; i++)
arr[i] = new int[kol];
int rasst;
for (int i = 0; i < kol; i++) {
for (int j = i; j < kol; j++) {
if (i == j) /*Если одинаковые точки - заполняем нулями, чтобы получилась главная диагональ нулей */
{
arr[i][j] = 0;
continue;
}
do /*Ввод расстояния между узлами для заполнения матрицы смежности */
{
cout << "Введите расстояние от узла " << i << " до узла " << j << " --> ";
cin >> rasst;
} while (rasst < 1);
arr[i][j] = arr[j][i] = rasst;
}
}
//Вывод матрицы смежности
cout << endl << "Матрица смежности: ";
for (int i = 0; i < kol; i++) {
cout << endl;
for (int j = 0; j < kol; j++)
cout << setw(5) << arr[i][j];
}
int *route = new int[kol]; /* Маршрут (массив узлов сети, в которых мы побывали в порядке посещения) */
cout << endl;
char ans;
int start;
do {
for (int i = 0; i < kol; i++) //Заполняем массив -1
route[i] = -1;
do //Ввод стартового узла
{
cout << "Введите стартовый узел --> ";
cin >> start;
} while (start < 0 || start > kol - 1);
route[0] = start;
int now = start;
int path = 0; // длина уже пройденного пути
cout << "\nМаршрут:" << endl;
for (int i = 1; i < kol; i++) { /* i - индекс по маршруту и количество переходов, не считая возврата в стартовый узел */
int min = INT_MAX; int min_town = 0;
for (int j = 0; j < kol; j++) {
if (check(j, route, kol) && arr[now][j] < min && arr[now][j] > 0) { //Нахождение минимума
min = arr[now][j]; // запомнили текущий минимум
min_town = j; // запомнили номер узла для тек.мин.
}
}
/* здесь min - действительный минимум и min_town - номер узла с минимальным расстоянием от текущего */
path += min; // добавляем к общему пути
route[i] = min_town; // добавляем узел в маршрут
cout << setw(2) << now << " -> " << setw(2) << route[i] << " (расстояние " << min << ", путь " << path << ")" << endl;
now = route[i];
}
// обрабатываем возврат в стартовый узел
path += arr[start][now];
cout << setw(2) << now << " -> " << setw(2) << start << " (расстояние " << arr[start][now] << ", путь " << path << ")" << endl;
cout << "Общая длина пройденного пути: " << path << endl;
cout << endl << "Желаете продолжить поиск путей?(+, если да) --> ";
cin >> ans;
} while (ans == '+');
delete[] route; //Удаление массива пройденных узлов
//Удаление матрицы смежности
for (int i = 0; i < kol; i++)
delete[] arr[i];
delete[] arr;
system("pause");
return 0;}