Пользователь
0,0
рейтинг
8 октября 2010 в 20:57

Разработка → Алгоритм Флойда — Уоршелла

Алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования. Это базовый алгоритм, так что тем кто его знает — можно дальше не читать.

Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (Robert Floyd) и Стивена Уоршелла (Stephen Warshall) в 1962 г., хотя в 1959 г. Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.

Ремарка


Если граф не содержит рёбер с отрицательным весом, то для решения этой проблемы можно использовать алгоритм Дейкстры для нахождения кратчайшего пути от одной вершины до всех остальных, запустив его на каждой вершине. Время работы такого алгоритма зависит от типа данных, который мы будем использовать для алгоритма Дейкстры, это может быть как простая очередь с приоритетом, так и бинарная или фибоначчиева Куча, соответственно время работы будет варьироваться от O(V3) до O(V*E*log(V)), где V количество вершин, а E — рёбер. («О»-большое).

Если же есть рёбера с отрицательным весом, можно использовать алгоритм Беллмана — Форда. Но этот алгоритм, запущенный на всех вершинах графа, медленнее, время его работы O(V2*E), а в сильно «густых» графах аж O(V4).

Динамическое программирование


Что значит динамический алгоритм? Динамическое программирование — это альтернатива решению задач методом «в лоб», то есть brute forc'ом или жадными алгоритмами. Используется там, где оптимальное решение подзадачи меньшего размера может быть использовано для решения исходной задачи. В общем виде метод выглядит так:

1. Разбиение задачи на подзадачи меньшего размера.
2. Нахождение оптимального решения подзадач рекурсивно.
3. Использование полученного решения подзадач для конструирования решения исходной задачи.

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

Структура кратчайшего пути


В основе алгоритма лежат два свойства кратчайшего пути графа. Первое:

Имеется кратчайший путь p1k=(v1,v2,… ,vk) от вершины v1 до вершины vk, а также его подпуть p'(vi,vi+1,… ,vj), при этом действует 1 <= i <= j <= k.

Если p — кратчайший путь от v1 до vk, то p' также является кратчайшим путем от вершины vi до vj

Это можно легко доказать, так как стоимость пути p складывается из стоимости пути p' и стоимости остальных его частей. Так вот представив что есть более короткий путь p', мы уменьшим эту сумму, что приведет к противоречию с утверждением, что эта сумма и так уже была минимальной.

Второе свойство является основой алгоритма. Мы рассматриваем граф G с пронумерованными от 1 до n вершинами {v1,v2,… ,vn} и путь pij от vi до vj, проходящий через определенное множество разрешенных вершин, ограниченное индексом k.

То есть если k=0, то мы рассматриваем прямые соединения вершин друг с другом, так как множество разрешенных промежуточных вершин рано нулю. Если k=1 — мы рассматриваем пути, проходящие через вершину v1, при k=2 — через вершины {v1, v2}, при k=3 — {v1, v3, v3} и так далее.

Например у нас есть такой граф (слева) и k=1, то есть в качестве промужуточных узлов разрешен только узел «1». В этом графе при k=1 нет пути p43, но есть при k=2, тогда можно добраться из «4» в «3» через «2» или через «1» и «2».

Рассмотрим кратчайший путь pij с разрешенными промужуточными вершинами {1..k-1} стоимостью dij. Теперь расширим множество на k- тый элемент, так что множество разрешенных вершин станет {1..k}. При таком расширении возможно 2 исхода:

Случай 1. Элемент k не входит в кратчайший путь pij, то есть от добавления дополнительной вершины мы ничего не выиграли и ничего не изменили, а значит стоимость кратчайшего пути dkij не изменился, соответственно

dkij = dk-1ij — просто перенимаем значение до увеличения k.

Случай 2. Элемент k входит в кратчайший путь pij, то есть после добавления новой вершины в можество разрешенных, кратчайший путь изменился и проходит теперь через вершину vk. Какую стоимость получит новый путь?

Новый кратчайший путь разбит вершиной vk на pik и pkj, используем первое свойство, согласно ему, pik и pkj также кратчайшие пути от vi до vk и от vk до vj соответственно. Значит

dkij = dkik + dkkj

А так как в этих путях k либо конечный, либо начальный узел, то он не входит в множество промежуточных, соответственно его из него можно удалить:
dkij = dk-1ik + dk-1kj

Алгоритм


Посмотрим на значение dkij в обоих случаях — верно! оно в обоих случаях складывается из значений d для k-1, а значит имея начальные (k=0) значения для d, мы сможем расчитать d для всех последующих значений k. А значения d для k=0 мы знаем, это вес/стоимость рёбер графа, то есть соединений без промужуточных узлов.

При k=n (n — количество вершин) мы получим оптимальные значения d для всех пар вершин.

При увеличении с k-1 до k, какое значение мы сохраним для dkik? Минимумом значений случая 1 и 2, то есть смотрим дешевле ли старый путь или путь с добавлением дополнительной вершины.



Псевдокод


Наконец сам алгоритм. Мы используем представление графа в виде матрицы cмежностей.



Как видно алгоритм очень прост — сначала происходит инициализация матрицы кратчайших расстояний D0, изначально она совпадает с матрицей смежности, в цикле увеличиваем значение k и пересчитываем матрицу расстояний, из D0 получаем D1, из D1 — D2 и так далее до k=n.

Предполагается, что если между двумя какими-то вершинами нет ребра, то в матрице смежности было записано какое-то большое число (достаточно большое, чтобы оно было больше длины любого пути в этом графе); тогда это ребро всегда будет невыгодно брать, и алгоритм сработает правильно. Правда, если не принять специальных мер, то при наличии в графе рёбер отрицательного веса, в результирующей матрице могут появиться числа вида ∞-1, ∞-2, и т.д., которые, конечно, по-прежнему означают, что между соответствующими вершинами вообще нет пути. Поэтому при наличии в графе отрицательных рёбер алгоритм Флойда лучше написать так, чтобы он не выполнял переходы из тех состояний, в которых уже стоит «нет пути»

Пример




Первый пересчет матрицы — изменяется одно значение, из-за расширения множества разрешенных вершин на вершину «1» мы смогли добраться от вершины «4» до «2», используя более дешевый путь.

dkij = min( dk-1ij; dk-1ik + dk-1kj )

d142 = min( d042, d041 + d012)

d142 = min( 4, -1)

Вторая итерация, улучшили значение для p43



Результат



Тут и там можно поиграть с аплетом и посмотреть как в живую работает алгоритм.

Анализ времени работы и использования памяти


Алгоритму требуется O(n3) памяти, для сохранения матриц. Однако количество матриц можно легко сократить до двух, каждый раз переписывая ненужную матрицу или вообще перейти к двухмерной матрице, убрав индекс k у dkij. Лучший вариант, который чаще всего используется — писать сразу в матрицу смежности, тогда нам совсем не нужна дополнительная память, правда если сразу переписывать изначальную матрицу, то нужно дополнительно показать корректность алгоритма, так как классическое академическоле доказательство верно только для случая, когда матрица предыдущей итерации не изменяется.

Что касается времени работы — три вложенных цикла от 1 до n — Θ(n3).

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


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

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

Реконструирование пути


Матрица расстояний покажет нам кратчайшее (самое дешевое) растояние для любой пары вершин, а как же узнать путь? Очень просто, при расчете dkij нужно расчитать еще и πkij. πkij при этом — предшественник вершины vj на пути от vi с множеством разрешенных промежуточных вершин {1..k}.

Я просто оставлю это сдесь, остально додумать может каждый сам



Применение


Как и любой базовый алгоритм, алгоритм Флойда — Уоршелла используется очень широко и много где, начиная от поиска транзитивного замыкания графа, заканчивая генетикой и управлением проектами. Но первое что приходит в голову конечно же транспортные и всякие другие сети.

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





На этом всё, написано не очень, так что если укажите на ошибки, несостыковки, непонятки и прочее, буду благодарен, текст мне этот еще нужен будет :)

Спасибо Rustam'у и mastersobg'у за поправки
Кысь @k_s
карма
66,2
рейтинг 0,0
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (32)

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

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

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

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

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

    Собственно, так оно и реализовано в GPS-навигаторах :)
    • 0
      Сомневаюсь, что этот алгоритм используется в навигаторах — там обычно нет необходимости рассчитывать кратчашие пути изо всех во все точки сразу. Да и слишком долгое это дело )
  • +1
    Люблю красивые хабратопики, спасибо.
  • 0
    В спортивном ориентировании можно было бы применять, вот только жаль, что невооруженным мозгом на лету не осилить этот алгоритм :( Но для анализа карт для ориентирования вполне подходит.
    • 0
      Точнее даже не «вполне подходит», а «самое то».
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    необязательно использовать параметр k в динамике — соответственно можно хранить двумерную матрицу ответа. итого памяти О(n^2).
    да, тут очень наглядное объяснение флойда
    www.intuit.ru/department/algorithms/baseadvalgos/3/
    • 0
      Я вроде написал, что память дополнительную можно вообще не использовать.

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

      Ну и просто для копилки блога Алгоритмы :D
  • 0
    Почему везде оговаривают, что граф не должен иметь отрицательных циклов? Алгоритм Флойда отлично справляется и с такой экзотикой. Достаточно к пути, проходящему через вершину i, добавлять поправку Wi = {0, если Dii >= 0; -Inf, если Dii < 0}.
    • 0
      автор имеет в виду, что флойд неверно будет работать, если путь будет проходить через цикл отрицательного веса(расстояние там равно минус бесконечности, а в матричке будет другое число)
    • +1
      добавил «Случай отрицательных циклов»
  • 0
    >> «Скажем если вы возьмете карту города — её транспортная система это граф,»
    Нужно допольнительно отметить, что карта города — это граф, в котором |E| примерно равно |V|, поэтому алгоритм Флойда будет сильно расточительным. Представьте, всего 10000 вершин достаточно, чтобы он работал НЕ быстро. А вот Дейкстра с обычной кучей окажется намного быстрее.
  • 0
    Теперь таксисты во всеоружии.
    • 0
      И не мечтайте. У них для определения маршрута всегда действует алгоритм «Дорогу покажешь?».
  • 0
    У нас банкоматы используют жадный алгоритм:
    Заряжен он банкнотами по 50 и 20 у.е. Просишь у него 80 (4 шт по 20).
    Алгоритм сперва (жадно) откладывает 50, потом понимает что из оставшихся банкнот 30 не составишь, обламывается и предлагает снять 70 или 90.
    • 0
      facepalm.jpg
      Подумал что новый топик на тему жадных алгоритмов и решил откомментировать обратную сторону их, как таковых.

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