Алгоритм Флойда-Уоршалла граф

@DmitryM5 · Регистрация: 27.08.2013

Author24 — интернет-сервис помощи студентам

Собственно мне дан ориентированный граф,в котором вес ребра между вершинами i и j допустим-это шанс добраться от вершины i к вершине j соответственно.
Ниже код ищет самые выгодные пути от вершин до всех остальных вершин.
Вопрос в том как доделать алгоритм,чтобы еще возможно было узнать через какие вершины проложен путь?
Не могу понять.Ниже подсказка
//Восстановление самих путей
Легко поддерживать дополнительную информацию — так называемых "предков", по которым можно будет восстанавливать сам кратчайший путь между любыми двумя заданными вершинами в виде последовательности вершин.

Для этого достаточно кроме матрицы расстояний d[][] поддерживать также матрицу предков p[][], которая для каждой пары вершин будет содержать номер фазы, на которой было получено кратчайшее расстояние между ними. Понятно, что этот номер фазы является не чем иным, как "средней" вершиной искомого кратчайшего пути, и теперь нам просто надо найти кратчайший путь между вершинами i и p[i][j], а также между p[i][j] и j. Отсюда получается простой рекурсивный алгоритм восстановления кратчайшего пути.

C++

vector<vector<double>> alg(vector<vector<double>> &g, int n) {
    for (int i = 0; i < n; ++i)
    for (int k = i+1; k < n; ++k)
    for (int j = k+1; j < n; ++j)
    if (g[i][j] < g[i][k] * g[k][j]) {
        g[i][j] = g[i][k] * g[k][j];
    }
    return g;
}

@Dani · 27.09.2014, 22:57

DmitryM5, если выполняется условие
Пишу прямо тут, поэтому 100% правильность не гарантирую

C++

for (int i = 0; i < n; ++i)
    for (int k = i+1; k < n; ++k)
    for (int j = k+1; j < n; ++j)
    if (g[i][j] < g[i][k] * g[k][j]) {
        g[i][j] = g[i][k] * g[k][j];
        p[i][j] = k;
    }

Теперь как восстановить путь из вершины i в вершину j:

C++

void way(int i, int j)
{
     if(i == j)
      std::cout << i;
     else
     {
          way(i, p[i][j]);
          std::cout << j;
     }
}

Как-то так.

Добавлено через 1 минуту
А вы уверены в правильности циклов в реализации алгоритма Флойда?

@ZaMaZaN4iK · 27.09.2014, 23:06

вот код точно работающего Флойда-Уоршелла:

C++

for (int k=0; k<n; ++k)
    for (int i=0; i<n; ++i)
        for (int j=0; j<n; ++j)
            d[i][j] = min (d[i][j], d[i][k] + d[k][j]);

для массива предков всё просто - там, где улучшаем путь, записываем также и предка.

ГРаф задан матрицей смежности

	27.09.2014, 23:06

Опции темы