Реализовал алгоритм Флойда, но задался вопросом,как сделать помимо вывода матрицы кратчайших путей, ещё и вывод матрицы расстояний, который показывает через какие точки нужно пройти,чтобы получился кратчайший путь. (Пример как выглядит матрица расстояний на скрине)
#include <iostream>
using namespace std;
int** mas = NULL;
int kol = 0;
//вычисление минимального пути по Флойду
void minFL(int** m, int kl)
{
for (int k = 0; k < kl; k++) {
for (int i = 0; i < kl; i++) {
for (int j = 0; j < kl; j++) {
if(m[i][j]>m[i][k]+m[k][j])
{
m[i][j] = m[i][k] + m[k][j];
}
}
}
}
}
int main()
{
setlocale(LC_ALL, "ru");
cout << "Введите число вершин графа" << endl;
cin >> kol;
if (kol < 1) {
return 0;
}
mas = new int* [kol];
for (int i = 0; i < kol; i++) mas[i] = new int[kol];
cout << "Введите матрицу смежности графа:" << endl;
for (int i = 0; i < kol; i++)
for (int j = 0; j < kol; j++) cin >> mas[i][j];
minFL(mas, kol);
cout << "Минимальные пути между вершинами:" << endl;
for (int i = 0; i < kol; i++) {
for (int j = 0; j < kol; j++) {
cout << mas[i][j] << " ";
}
cout << endl;
}
return 0;