3 / 3 / 1
Регистрация: 07.07.2012
Сообщений: 90
1

Алгоритм Флойда — Уоршелла. Как же найти путь?

21.11.2013, 00:39. Показов 2150. Ответов 5
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Реализовал нахождение длин кратчайшего пути между вершинами, но как найти сам путь так и не смог понять.

Подскажите, пожалуйста.

Собственно реализация вот:
C++
1
2
3
4
5
6
7
8
9
10
11
12
    for (size_t k(0); k < MatrixLen; ++k)
        for (size_t i(0); i < MatrixLen; ++i)
            for (size_t j(0); j < MatrixLen; ++j)
                if (matrix[i][k] < INF && matrix[k][j] < INF)
                {
                    if (matrix[i][k] + matrix[k][j] < matrix[i][j])
                    {
                        matrix[i][j] = matrix[i][k] + matrix[k][j];
                        parents[i][j] = k;
                    }
                }
            }

Возможно ли использование этого алгоритма с массивами типа N x M (Не квадратными матрицами), то есть со сторонами разной длины.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.11.2013, 00:39
Ответы с готовыми решениями:

Алгоритм флойда - уоршелла находит не все пути
Пытаюсь реализовать этот алгоритм под c# и unity. вот создание начальных матриц. ...

Алгоритм Флойда-Уоршелла [для нахождения кратчайших путей]
Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин...

Найти медиану графа (алгоритм Флойда-Уоршелла)
Задача: найти медиану графа, т.е такую его вершину. что сумма расстояний от нее до остальных вершин...

Алгоритм Флойда-Уоршелла
Вечно какая-то засада и кругом враги! :-) Разбирался я в алгоритме Уоршелла. И вот какая проблема:...

5
833 / 641 / 101
Регистрация: 20.08.2013
Сообщений: 2,524
21.11.2013, 18:19 2
Цитата Сообщение от Flaker Посмотреть сообщение
Возможно ли использование этого алгоритма с массивами типа N x M
Это же матрица смежности по сути, соответственно в ней число строк равно числу вершин и число столбцов развно числу вершин.
Что ты хочешь сделать, чтобы она оказалась неквадратной?

Цитата Сообщение от Flaker Посмотреть сообщение
но как найти сам путь так и не смог понять
Массив parents содержит промежуточные вершины:
Код
a ~> b
a ~> p[a,b] ~> b
a ~> p[a,p[a,b]] ~> p[a,b] ~> p[p[a,b],b] ~> b
...
a -> x[1] -> x[2] -> ... -> x[k] -> b
На псевдокоде как-то так:
Код
path(a,b) => p[a,b] ? path(a,p[a,b]) & path(p[a,b],b) : {a,b}
где объединение путей выкидывает совпадающую вершину.
1
3 / 3 / 1
Регистрация: 07.07.2012
Сообщений: 90
22.11.2013, 02:50  [ТС] 3
Это же матрица смежности по сути, соответственно в ней число строк равно числу вершин и число столбцов развно числу вершин.
Понял, спасибо.

А вот про parents можно поподробнее? Я не совсем понимаю этот псевдокод...

В моем коде "parents[i][j] = k" верно?

Что значит a ~> b, p[a,b] и т.д.?
p у вас в псевдокоде это мой массив parents?
0
833 / 641 / 101
Регистрация: 20.08.2013
Сообщений: 2,524
22.11.2013, 09:57 4
Цитата Сообщение от Flaker Посмотреть сообщение
В моем коде "parents[i][j] = k" верно?
Да. Если сумма длин путей i ~> k и k ~> j меньше чем текущая длина i ~> j, то надо идти i ~> k ~> j.

Цитата Сообщение от Flaker Посмотреть сообщение
p у вас в псевдокоде это мой массив parents?
Да.

Цитата Сообщение от Flaker Посмотреть сообщение
Что значит a ~> b
Вроде стандартные обозначения:
a ~> b - путь из a в b, возможно через промежуточные вершины
a -> b - путь из a в b без промежуточных вершин, т. е. ребро

Цитата Сообщение от Flaker Посмотреть сообщение
Я не совсем понимаю этот псевдокод...
Рекурсивно:
Код
a ~> b := если есть p[a,b] то a ~> p[a,b] ~> b иначе a -> b
1
3 / 3 / 1
Регистрация: 07.07.2012
Сообщений: 90
23.11.2013, 03:52  [ТС] 5
Qwertiy, спасибо за ответы.

Все равно не могу понять, как в коде реализовать...

Воспользовавшись информацией из этого поста, написал так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    Path.push(from);
    Goals.push(to);
 
    while(!Goals.empty())
    {
        int u = Path.top();
        int v = Goals.top();
        int s = parents[u][v];
        if(v == s)
        {
            Path.push(v);
            Goals.pop();
        }
        else
            Goals.push(s);
    }
Но программа в бесконечный цикл попадает...
Что не верно?
0
833 / 641 / 101
Регистрация: 20.08.2013
Сообщений: 2,524
23.11.2013, 10:49 6
Чем рекурсивный вариант не устраивает?
0
23.11.2013, 10:49
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.11.2013, 10:49
Помогаю со студенческими работами здесь

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

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

Алгоритм Флойда-Уоршелла
Народ подскажите , а как реализовать этот алгоритм на Delphi ?

Алгоритм Флойда - Уоршелла программная реализация
Господа. Делфи изучаю несколько дней. Нужно реализваовать алгоритм. Нашел тут и тут примеры. ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru