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

[alexol]

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

[IeN]

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

[k_s]

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

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

[mastersobg]

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

[k_s]

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

[mastersobg]

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

[k_s]

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

[Zealint]

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

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

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

[tagir_valeev]

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

[k_s]

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

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

[tagir_valeev]

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

[Mezomish]

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

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

[Regis]

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

[Levsha100]

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

[Rustam]

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

[k_s]

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

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

[Rustam]

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

[k_s]

А, понятно

[Saska]

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

[k_s]

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

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

[apangin]

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

[Rustam]

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

[k_s]

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

[Zealint]

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

[Khoth]

Теперь таксисты во всеоружии.

[xn__p2a]

И не мечтайте. У них для определения маршрута всегда действует алгоритм «Дорогу покажешь?».

[nanshakov]

картинки умерли. Стало не читаемо.