k_s 8 окт 2010 в 20:57

Алгоритм Флойда — Уоршелла

6 мин

168K

Алгоритмы*

+120

Комментарии 33

alexol 8 окт 2010 в 21:36

На главную да еще с такой мего картинкой… пожалейте хостера

IeN 8 окт 2010 в 21:52

мм этот алгоритм мне помог получить в универе отлично… =)
хотя до конца я его понял как раз на экзамене

k_s 8 окт 2010 в 21:57

Кстати что меня ударило написать этот пост! Неделю назад обнаружилось, что у меня не сдан экзамен по структурам данных и алгоритмам двухлетней давности и вот сегодня и сходил и сдал его, в основном говорили о динамических алгоритмах, и больше всего о данном. Знание того, на каких принципах он основан, помогло мне сдать экзамен без подготовки :D

Так что всем студентам — это очень полезный алгоритм! :D

mastersobg 8 окт 2010 в 22:00

1. Время работы Дейкстры с heap-ом — O(E*log(V)), а не O(E*log(E)) как Вы написали.
2. Алгоритм Форда-Беллмана работает за O(V*E), а не O(V^4).

k_s 8 окт 2010 в 22:06

Да, Дейкстра на хипе срабоатет в данном контексте за O(V*E*log(V)), поправил, а Форд-Беллман O(V²E) и при очень густом это выльется в O(V⁴), речь же не о оригинальном влгоритме, а о его использовании для данной задачи, то есть алгоритм будет выполняться не на одном узле, а на всех.

mastersobg 8 окт 2010 в 22:10

«Но этот алгоритм медленнее, время его работы, особенно в сильно «густых» графах, лежит в O(V4)»
Меня смутила эта фраза. Я подумал, что Вы говорите именно о Форд-Беллмане. Вы же имели в виду ещё просчёт для всех вершин, т.е. O(v^4) в целом. :)

k_s 8 окт 2010 в 22:11

Сейчас сформулирую получше

Zealint 9 окт 2010 в 08:13

Всё неправильно:
Если куча обычная, то O(E*log(V)), а на всех вершинах будет O(V*E*log(V)) (автор прав).
Если куча Фибоначчи, то O(V*log(V) + E), а на всех вершинах O(V^2*log(V) + VE), что по теории быстрее, чем Флойд (на почти всех графах), но на практике никуда не годится совсем.

>> «то нужно дополнительно показать корректность алгоритма, так как классическое академическоле доказательство верно только для случая, когда матрица предыдущей итерации не изменяется.»

Так показали бы.

tagir_valeev 8 окт 2010 в 22:10

Дискретка, второй курс =) Помню, маялись, рисовали эти таблички :-)

k_s 8 окт 2010 в 22:14

Сам алгоритм прост как консервная банка, а вот знать как он работает полезно.

Таблички пару лет назад тоже рисовал, тока вот зачем? Делать то что написано в алгоритме не трудно.

tagir_valeev 8 окт 2010 в 22:19

Известно зачем — чтобы пятёрку получить =)
На самом деле непонятно, как лучше отложится — если реализовать его самому в программном коде или выполнить пару раз на бумаге вручную :-)

Mezomish 8 окт 2010 в 22:13

>Скажем если вы возьмете карту города — её транспортная система это граф, соответственно присвоив каждой грани некую стоимость, расчитанную скажем из пропускной способности и других важный параметров — вы сможете подвести попутчика по самому короткому/быстрому/дешевому пути.

Собственно, так оно и реализовано в GPS-навигаторах :)

Regis 9 окт 2010 в 04:32

Сомневаюсь, что этот алгоритм используется в навигаторах — там обычно нет необходимости рассчитывать кратчашие пути изо всех во все точки сразу. Да и слишком долгое это дело )

Levsha100 8 окт 2010 в 22:27

Люблю красивые хабратопики, спасибо.

НЛО прилетело и опубликовало эту надпись здесь

Rustam 9 окт 2010 в 03:56

необязательно использовать параметр k в динамике — соответственно можно хранить двумерную матрицу ответа. итого памяти О(n^2).
да, тут очень наглядное объяснение флойда
www.intuit.ru/department/algorithms/baseadvalgos/3/

k_s 9 окт 2010 в 04:36

Я вроде написал, что память дополнительную можно вообще не использовать.

Если бы мне в школе а таком темпе рассказали — я бы конечно запомнил алгоритм, но не понял бы как он работает :)

Rustam 9 окт 2010 в 05:11

не, вы не поняли. Для того, чтобы хранить матрицу смежности, нужно О(n^2) памяти. В вашем случае для того, чтобы считать матрицу, нужно трехмерная матрица(d[i][j][k]). Ну так вот: можно избавиться от третьего параметра. Прошу дополнить пост =)

НЛО прилетело и опубликовало эту надпись здесь

k_s 9 окт 2010 в 13:10

А, понятно

Saska 9 окт 2010 в 04:30

Эх, курсовик помню по нему писал на 1-ом курсе :)
Хотя не понимаю зачем всё было так расписывать, тут всего 3 вложенных цикла и условный оператор — алгоритм-то простейший.

k_s 9 окт 2010 в 04:39

Знать алгоритм и понимать почему и как он работает — немного разнве вещи. Алгоритм конечно же не трудный, но вот так спроси — вряд ли много кто сходу сразу скажет почему формула для d выглядит именно так.

Ну и просто для копилки блога Алгоритмы :D

apangin 9 окт 2010 в 05:23

Почему везде оговаривают, что граф не должен иметь отрицательных циклов? Алгоритм Флойда отлично справляется и с такой экзотикой. Достаточно к пути, проходящему через вершину i, добавлять поправку Wi = {0, если Dii >= 0; -Inf, если Dii < 0}.

Rustam 9 окт 2010 в 05:42

автор имеет в виду, что флойд неверно будет работать, если путь будет проходить через цикл отрицательного веса(расстояние там равно минус бесконечности, а в матричке будет другое число)

k_s 9 окт 2010 в 13:42

добавил «Случай отрицательных циклов»

Zealint 9 окт 2010 в 08:17

>> «Скажем если вы возьмете карту города — её транспортная система это граф,»
Нужно допольнительно отметить, что карта города — это граф, в котором |E| примерно равно |V|, поэтому алгоритм Флойда будет сильно расточительным. Представьте, всего 10000 вершин достаточно, чтобы он работал НЕ быстро. А вот Дейкстра с обычной кучей окажется намного быстрее.