Pull to refresh

Comments 33

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

Так что всем студентам — это очень полезный алгоритм! :D
1. Время работы Дейкстры с heap-ом — O(E*log(V)), а не O(E*log(E)) как Вы написали.
2. Алгоритм Форда-Беллмана работает за O(V*E), а не O(V^4).
Да, Дейкстра на хипе срабоатет в данном контексте за O(V*E*log(V)), поправил, а Форд-Беллман O(V2E) и при очень густом это выльется в O(V4), речь же не о оригинальном влгоритме, а о его использовании для данной задачи, то есть алгоритм будет выполняться не на одном узле, а на всех.
«Но этот алгоритм медленнее, время его работы, особенно в сильно «густых» графах, лежит в O(V4)»
Меня смутила эта фраза. Я подумал, что Вы говорите именно о Форд-Беллмане. Вы же имели в виду ещё просчёт для всех вершин, т.е. O(v^4) в целом. :)
Сейчас сформулирую получше
Всё неправильно:
Если куча обычная, то O(E*log(V)), а на всех вершинах будет O(V*E*log(V)) (автор прав).
Если куча Фибоначчи, то O(V*log(V) + E), а на всех вершинах O(V^2*log(V) + VE), что по теории быстрее, чем Флойд (на почти всех графах), но на практике никуда не годится совсем.

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

Так показали бы.
Дискретка, второй курс =) Помню, маялись, рисовали эти таблички :-)
Сам алгоритм прост как консервная банка, а вот знать как он работает полезно.

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

Собственно, так оно и реализовано в GPS-навигаторах :)
Сомневаюсь, что этот алгоритм используется в навигаторах — там обычно нет необходимости рассчитывать кратчашие пути изо всех во все точки сразу. Да и слишком долгое это дело )
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
необязательно использовать параметр k в динамике — соответственно можно хранить двумерную матрицу ответа. итого памяти О(n^2).
да, тут очень наглядное объяснение флойда
www.intuit.ru/department/algorithms/baseadvalgos/3/
Я вроде написал, что память дополнительную можно вообще не использовать.

Если бы мне в школе а таком темпе рассказали — я бы конечно запомнил алгоритм, но не понял бы как он работает :)
не, вы не поняли. Для того, чтобы хранить матрицу смежности, нужно О(n^2) памяти. В вашем случае для того, чтобы считать матрицу, нужно трехмерная матрица(d[i][j][k]). Ну так вот: можно избавиться от третьего параметра. Прошу дополнить пост =)
UFO just landed and posted this here
Эх, курсовик помню по нему писал на 1-ом курсе :)
Хотя не понимаю зачем всё было так расписывать, тут всего 3 вложенных цикла и условный оператор — алгоритм-то простейший.
Знать алгоритм и понимать почему и как он работает — немного разнве вещи. Алгоритм конечно же не трудный, но вот так спроси — вряд ли много кто сходу сразу скажет почему формула для d выглядит именно так.

Ну и просто для копилки блога Алгоритмы :D
Почему везде оговаривают, что граф не должен иметь отрицательных циклов? Алгоритм Флойда отлично справляется и с такой экзотикой. Достаточно к пути, проходящему через вершину i, добавлять поправку Wi = {0, если Dii >= 0; -Inf, если Dii < 0}.
автор имеет в виду, что флойд неверно будет работать, если путь будет проходить через цикл отрицательного веса(расстояние там равно минус бесконечности, а в матричке будет другое число)
добавил «Случай отрицательных циклов»
>> «Скажем если вы возьмете карту города — её транспортная система это граф,»
Нужно допольнительно отметить, что карта города — это граф, в котором |E| примерно равно |V|, поэтому алгоритм Флойда будет сильно расточительным. Представьте, всего 10000 вершин достаточно, чтобы он работал НЕ быстро. А вот Дейкстра с обычной кучей окажется намного быстрее.
Теперь таксисты во всеоружии.
И не мечтайте. У них для определения маршрута всегда действует алгоритм «Дорогу покажешь?».
UFO just landed and posted this here
UFO just landed and posted this here
Only those users with full accounts are able to leave comments. Log in, please.