Алгоритм Беллмана-Форда представляет собой алгоритм , который вычисляет кратчайший путь из одного источника вершины до всех остальных вершин в весовом орграфа . [1] Он медленнее, чем алгоритм Дейкстры для той же задачи, но более универсален, поскольку он способен обрабатывать графы, в которых некоторые веса ребер являются отрицательными числами. Алгоритм был впервые предложен Альфонсо Шимбелем ( 1955 ), но вместо этого назван в честь Ричарда Беллмана и Лестера Форда-младшего , опубликовавших его в 1958 и 1956 годах соответственно. [2] Эдвард Ф. Мур также опубликовал вариант этого алгоритма в 1959 году , и по этой причине его также иногда называют алгоритмом Беллмана – Форда – Мура . [1]
Класс | Задача поиска кратчайшего пути с одним источником (для взвешенных ориентированных графов) |
---|---|
Структура данных | График |
Наихудшая производительность | |
Лучшая производительность | |
Сложность пространства в наихудшем случае |
Отрицательные веса ребер встречаются в различных приложениях графов, отсюда и полезность этого алгоритма. [3] Если граф содержит «отрицательный цикл» (т. Е. Цикл , сумма ребер которого равна отрицательному значению), достижимый из источника, тогда не существует самого дешевого пути: любой путь, имеющий точку на отрицательном цикле, может быть удешевляется еще одним обходом отрицательного цикла. В таком случае алгоритм Беллмана – Форда может обнаружить отрицательный цикл и сообщить о нем. [1] [4]
Алгоритм
Подобно алгоритму Дейкстры , Беллмана – Форда действует релаксация , при которой приближения к правильному расстоянию заменяются лучшими до тех пор, пока они в конечном итоге не достигнут решения. В обоих алгоритмах приблизительное расстояние до каждой вершины всегда является завышенным по сравнению с истинным расстоянием и заменяется минимумом его старого значения и длиной вновь найденного пути. Однако алгоритм Дейкстры использует очередь приоритетов для жадного выбора ближайшей вершины, которая еще не была обработана, и выполняет этот процесс релаксации на всех ее исходящих ребрах; напротив, алгоритм Беллмана – Форда просто расслабляет все края и делает это раз, где - количество вершин в графе. В каждом из этих повторений количество вершин с правильно рассчитанными расстояниями растет, из чего следует, что в конечном итоге все вершины будут иметь свои правильные расстояния. Этот метод позволяет применять алгоритм Беллмана – Форда к более широкому классу входных данных, чем алгоритм Дейкстры.
Вбегает Беллман – Форд время , где а также - количество вершин и ребер соответственно.
Функция BellmanFord ( список вершин, список ребер, вершин источника) является // Эта реализация принимает граф, представленный // списками вершин (представленных как целые числа [0..n-1]) и ребер, // и заполняет два массива (расстояние и предшественник), удерживая // кратчайший путь от источник для каждой вершины расстояние: = список размера n предшественник: = список размера n // Шаг 1: инициализируем граф для каждой вершины v в вершинах do distance [v]: = inf // Инициализируем расстояние до всех вершин до бесконечности предшественник [v]: = null // И имеющий нулевого предшественника distance [source]: = 0 // Расстояние от источника до самого себя, конечно же, ноль // Шаг 2: расслабление ребер многократно повторяется | V | −1 раз : для каждого ребра (u, v) с весом w в ребрах do if distance [u] + wто расстояние [v]: = расстояние [u] + w предшественник [v]: = u // Шаг 3: проверка циклов с отрицательным весом для каждого ребра (u, v) с весом w в ребрах выполняется, если distance [u] + w то ошибка «График содержит цикл с отрицательным весом» расстояние возврата , предшественник
Проще говоря, алгоритм инициализирует расстояние до источника равным 0, а все остальные узлы - бесконечностью. Затем для всех краев, если расстояние до пункта назначения можно сократить, взяв край, расстояние обновляется до нового более низкого значения. На каждой итерации я , что края сканированные, алгоритм находит все кратчайшие пути по большей длине я ребра (и , возможно , некоторые пути длиннее , чем я края). Поскольку максимально длинный путь без цикла может быть края, края необходимо сканировать раз, чтобы найти кратчайший путь для всех узлов. Выполняется окончательное сканирование всех краев, и если какое-либо расстояние обновляется, то путь длины были найдены ребра, которые могут возникнуть только в том случае, если в графе существует хотя бы один отрицательный цикл.
Доказательство правильности
Правильность алгоритма можно показать по индукции :
Лемма . После того, как я повторения для цикла,
- если Distance ( u ) не бесконечно, оно равно длине некоторого пути от s до u ; а также
- если существует путь от s до u с не более чем i ребрами, тогда Distance (u) - это не более чем длина кратчайшего пути от s до u с не более чем i ребрами.
Доказательство . Для базового случая индукции, рассмотрим i=0
и момент , прежде чем для цикла выполняются в первый раз. Затем для исходной вершины source.distance = 0
, что правильно. Для других вершин u , что также верно, потому что нет пути от источника до u с 0 ребрами.u.distance = infinity
Для индуктивного случая сначала докажем первую часть. Рассмотрим момент, когда расстояние до вершины обновляется на v.distance := u.distance + uv.weight
. По предположению индукции u.distance
- длина некоторого пути от источника до u . Затем u.distance + uv.weight
- длина пути от источника до v, который следует по пути от источника до u, а затем идет к v .
Для второй части рассмотрим кратчайший путь P (их может быть более одного) от источника до v с не более чем i ребрами. Пусть u будет последней вершиной перед v на этом пути. Тогда часть пути от источника до u является кратчайшим путем от источника до u с не более чем i-1 ребрами, поскольку в противном случае должен существовать какой-то строго более короткий путь от источника до u с не более i- 1 ребро, и затем мы могли бы добавить ребро uv к этому пути, чтобы получить путь с не более чем i ребрами, который строго короче P - противоречие. По предположению индукции, u.distance
после i −1 итераций длина пути от источника до u не превышает длины . Таким образом, uv.weight + u.distance
самый большая длина P . На i- й итерации v.distance
сравнивается с uv.weight + u.distance
, и устанавливается равным ему, если uv.weight + u.distance
меньше. Следовательно, после i итераций v.distance
это не более длины P , т. Е. Длины кратчайшего пути от источника до v, который использует не более i ребер.
Если нет циклов с отрицательным весом, то каждый кратчайший путь посещает каждую вершину не более одного раза, поэтому на шаге 3 дальнейшие улучшения не могут быть сделаны. И наоборот, предположим, что нельзя добиться улучшения. Тогда для любого цикла с вершинами v [0], ..., v [ k −1],
v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight
Суммируя по циклу, члены v [ i ] .distance и v [ i −1 (mod k )]. Distance сокращаются, оставляя
0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight
Т.е. каждый цикл имеет неотрицательный вес.
Обнаружение отрицательных циклов
Когда алгоритм используется для поиска кратчайших путей, наличие отрицательных циклов является проблемой, не позволяющей алгоритму найти правильный ответ. Однако, поскольку он завершается при обнаружении отрицательного цикла, алгоритм Беллмана – Форда может использоваться для приложений, в которых необходимо искать эту цель - например, в методах отмены цикла в анализе сетевого потока . [1]
Приложения в маршрутизации
Распределенный вариант алгоритма Беллмана – Форда используется в протоколах маршрутизации с вектором расстояния , например в протоколе маршрутной информации (RIP). Алгоритм распределен, потому что он включает несколько узлов (маршрутизаторов) в автономной системе (AS) , совокупность IP-сетей, обычно принадлежащих интернет-провайдеру. Он состоит из следующих этапов:
- Каждый узел вычисляет расстояния между собой и всеми другими узлами в AS и сохраняет эту информацию в виде таблицы.
- Каждый узел отправляет свою таблицу всем соседним узлам.
- Когда узел получает таблицы расстояний от своих соседей, он вычисляет кратчайшие маршруты ко всем другим узлам и обновляет свою собственную таблицу, чтобы отразить любые изменения.
Основные недостатки алгоритма Беллмана – Форда в этой настройке следующие:
- Он плохо масштабируется.
- Изменения в топологии сети не отражаются быстро, поскольку обновления распространяются от узла к узлу.
- Считайте до бесконечности, если сбои канала или узла делают узел недоступным для некоторого набора других узлов, эти узлы могут бесконечно постепенно увеличивать свои оценки расстояния до него, а тем временем могут возникать петли маршрутизации.
Улучшения
Алгоритм Беллмана – Форда может быть улучшен на практике (хотя и не в худшем случае) путем наблюдения, что если итерация основного цикла алгоритма завершается без внесения каких-либо изменений, алгоритм может быть немедленно остановлен, поскольку последующие итерации будут больше не вносить изменений. С этим условием раннего завершения основной цикл может в некоторых случаях использовать намного меньше, чем | V | - 1 итерация, хотя худший вариант алгоритма остается без изменений. Все следующие улучшения поддерживают наихудшая временная сложность.
Вариант алгоритма Беллмана-Форда, известный как алгоритм кратчайшего пути и быстрее , впервые описанный Муром (1959) , сокращает количество шагов релаксации, которые необходимо выполнить на каждой итерации алгоритма. Если вершина v имеет значение расстояния, которое не изменилось с момента последнего ослабления ребер из v , тогда нет необходимости ослаблять ребра из v во второй раз. Таким образом, по мере роста числа вершин с правильными значениями расстояния, количество исходящих ребер, которые необходимо ослаблять на каждой итерации, сокращается, что приводит к экономии времени с постоянным коэффициентом для плотных графов .
Йен (1970) описал еще одно усовершенствование алгоритма Беллмана – Форда. Его усовершенствование сначала назначает произвольный линейный порядок всем вершинам, а затем разбивает множество всех ребер на два подмножества. Первое подмножество E f содержит все ребра ( v i , v j ) такие, что i < j ; вторая, E b , содержит ребра ( v i , v j ) такие, что i > j . Каждая вершина посещается в порядке v 1 , v 2 , ..., v | V | , расслабляя каждое выходящее из этой вершины ребро в E f . Затем каждую вершину посещают в порядке v | V | , v | V | −1 , ..., v 1 , расслабляя каждое выходящее из этой вершины ребро в E b . Каждая итерация основного цикла алгоритма после первой добавляет по крайней мере два ребра к набору ребер, релаксированные расстояния которых соответствуют правильным расстояниям кратчайшего пути: одно от E f и одно от E b . Эта модификация уменьшает наихудшее количество итераций основного цикла алгоритма с | V | - от 1 до. [5] [6]
Другое усовершенствование, выполненное Баннистером и Эппштейном (2012) , заменяет произвольный линейный порядок вершин, использованный во втором улучшении Йена, случайной перестановкой . Это изменение делает наихудший случай улучшения Йена (в котором края кратчайшего пути строго чередуются между двумя подмножествами E f и E b ) очень маловероятным. При случайном порядке перестановок вершин ожидаемое количество итераций, необходимых в основном цикле, не превышает. [6]
Заметки
- ^ a b c d Банг-Дженсен и Гутин (2000)
- ^ Шрайвер (2005)
- ^ Седжвик (2002) .
- ^ Клейнберг & Tardos (2006) .
- ^ Корменадр., 2е изд., Проблема 24-1, стр. 614-615.
- ^ a b См. веб-упражнения Седжвика по алгоритмам , 4-е изд., упражнения 5 и 12 (получено 30 января 2013 г.).
Рекомендации
Первоисточники
- Шимбель, А. (1955). Структура в сетях связи . Материалы симпозиума по информационным сетям. Нью-Йорк, Нью-Йорк: Политехническая пресса Политехнического института Бруклина. С. 199–203.
- Беллман, Ричард (1958). «О проблеме маршрутизации» . Квартал прикладной математики . 16 : 87–90. DOI : 10.1090 / QAM / 102435 . Руководство по ремонту 0102435 .
- Форд, Лестер Р. младший (14 августа 1956 г.). Теория сетевых потоков . Документ П-923. Санта-Моника, Калифорния: RAND Corporation.
- Мур, Эдвард Ф. (1959). Кратчайший путь через лабиринт . Proc. Междунар. Симпозиумы. Теория коммутации 1957 г., часть II. Кембридж, Массачусетс: Гарвардский университет. Нажмите. С. 285–292. Руководство по ремонту 0114710 .
- Йен, Джин Ю. (1970). «Алгоритм поиска кратчайших маршрутов от всех исходных узлов до заданного пункта назначения в общих сетях» . Квартал прикладной математики . 27 (4): 526–530. DOI : 10.1090 / QAM / 253822 . Руководство по ремонту 0253822 .
- Баннистер, MJ; Эппштейн, Д. (2012). Рандомизированное ускорение алгоритма Беллмана – Форда . Аналитическая алгоритмика и комбинаторика (ANALCO12), Киото, Япония. С. 41–47. arXiv : 1111.5414 . DOI : 10.1137 / 1.9781611973020.6 .
Вторичные источники
- Банг-Йенсен, Йорген; Гутин, Григорий (2000). «Раздел 2.3.4: Алгоритм Беллмана-Форда-Мура». Орграфы: теория, алгоритмы и приложения (Первое изд.). ISBN 978-1-84800-997-4.
- Шрайвер, Александр (2005). «К истории комбинаторной оптимизации (до 1960 г.)» (PDF) . Справочник по дискретной оптимизации . Эльзевьер: 1–68.
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. Введение в алгоритмы . MIT Press и McGraw-Hill., Второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 24.1: Алгоритм Беллмана – Форда, стр. 588–592. Задача 24-1, стр. 614–615. Третье издание. MIT Press, 2009. ISBN 978-0-262-53305-8 . Раздел 24.1: Алгоритм Беллмана – Форда, стр. 651–655.
- Heineman, Джордж Т .; Поллис, Гэри; Селькоу, Стэнли (2008). «Глава 6: Графические алгоритмы». Об алгоритмах в двух словах . O'Reilly Media . С. 160–164. ISBN 978-0-596-51624-6.
- Клейнберг, Джон ; Тардос, Ива (2006). Разработка алгоритмов . Нью-Йорк: Pearson Education, Inc.
- Седжвик, Роберт (2002). «Раздел 21.7: Отрицательные веса на краях». Алгоритмы на Java (3-е изд.). ISBN 0-201-36121-3. Архивировано из оригинала на 2008-05-31 . Проверено 28 мая 2007 .