Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
DmitryM5
Maria ->∞
106 / 86 / 44
Регистрация: 27.08.2013
Сообщений: 1,250
Записей в блоге: 1
1

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

27.09.2014, 20:59. Просмотров 1964. Ответов 2
Метки нет (Все метки)

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

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

C++
1
2
3
4
5
6
7
8
9
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;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.09.2014, 20:59
Ответы с готовыми решениями:

Алгоритм Флойда С++ реализация
Есть такой код класса Помогите, пожалуйста найти по методу Флойда самый короткий путь, он описан в...

Алгоритм Флойда Оршала
Найти наикратчайшее расстояние от каждой до каждой. Задание представляет собой любую матрицу 4*4....

Алгоритм Флойда-Уоршела
Ребят, помогите. На завтра нужно сдать алгоритм флойда. Вроде нашел код, но он не выводит САМО...

Алгоритм Флойда–Уоршелла
for (int k=0; k&lt;n; k++) for (int i=0; i&lt;n; i++) for (int j=0; j&lt;n; j++)как сделать так,...

Алгоритм Флойда - Уоршелла
не получается реализовать алгоритм Флойда-Уоршелла, вроде все должнен выводить, а выводит или нули...

2
Dani
1395 / 639 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
27.09.2014, 22:57 2
DmitryM5, если выполняется условие
Пишу прямо тут, поэтому 100% правильность не гарантирую
C++
1
2
3
4
5
6
7
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++
1
2
3
4
5
6
7
8
9
10
void way(int i, int j)
{
     if(i == j)
      std::cout << i;
     else
     {
          way(i, p[i][j]);
          std::cout << j;
     }
}
Как-то так.

Добавлено через 1 минуту
А вы уверены в правильности циклов в реализации алгоритма Флойда?
1
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
27.09.2014, 23:06 3
вот код точно работающего Флойда-Уоршелла:
C++
1
2
3
4
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]);
для массива предков всё просто - там, где улучшаем путь, записываем также и предка.

ГРаф задан матрицей смежности
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.09.2014, 23:06

В чем ошибка? Алгоритм Флойда
Не понимаю почему не запускается, может нужна еще кака-набудь библиотека? Программу нашел в...

Алгоритм Флойда (теория графов)
код: int** floid(int** W,int n){ vector&lt;int**&gt;D(n); int** A=new int*; for(int i=0;i&lt;n;i++){...

Самый короткий путь алгоритм Флойда
Не все тесты проходит, где ошибка? Дан ориентированный взвешенный полный граф, рёбрам которого...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru