1

Реализовал алгоритм Флойда, но задался вопросом,как сделать помимо вывода матрицы кратчайших путей, ещё и вывод матрицы расстояний, который показывает через какие точки нужно пройти,чтобы получился кратчайший путь. (Пример как выглядит матрица расстояний на скрине)

#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;

Матрица кратчайших путей и расстояний

1 ответ 1

3

Создайте массив для лучших соседей такого же размера.

В блоке оператора if рядом с обновлением m[i][j] добавьте

best[i][j] = best[i][k]

По окончанию работы основного алгоритма для данной пары вершин a,b пройдите от best[a][b], пока не упрётесь в b.

Пояснение: best[a][b] хранит вершину, в которую нужно пойти из вершины a, чтобы достичь b оптимально. Если мы перешли в вершину с, то теперь best[с][b] хранит вершину, в которую нужно пойти из вершины с, чтобы достичь b оптимально.

Начальная инициализация best - для каждой вершины best[a][a] = a, для ребра a-b best[a][b] = b, остальное заполнить спецзначением (например, -1)

Wiki

2
  • не особо понял, что нужно сделать по окончанию работы основного алгоритма
    – Cyber_Dezz
    5 ноя 2020 в 15:00
  • Алгоритм Флойда- Уоршелла даёт набор минимальных путей для всех пар вершин. Выбираете пару вершин, запускаете для неё восстановление оптимального маршрута. Надо для всех пар - для всех это делаете. Вот, кстати, в английской вики есть псевдокод
    – MBo
    5 ноя 2020 в 15:12

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.