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

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

27.09.2014, 20:59. Просмотров 2702. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.09.2014, 20:59
Ответы с готовыми решениями:

Алгоритм Флойда
Добрый вечер, помогите исправить ошибки в коде. #include &lt;iostream&gt; #include &lt;time.h&gt; #include...

Алгоритм Флойда Оршала
Найти наикратчайшее расстояние от каждой до каждой. Задание представляет собой любую матрицу 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
1401 / 643 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
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
Мой лучший друг-отладчик!
164 / 164 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.09.2014, 23:06

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

Реализовать алгоритм Флойда Уоршелла
Нужна помощь по написанию алгоритма по задаче представленной ниже: Туристическая фирма...

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


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

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

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