Алгоритм беллмана форда и дейкстры отличия

Добавил пользователь Евгений Кузнецов
Обновлено: 18.09.2024

После долгого гугления я обнаружил, что в большинстве источников говорится, что алгоритм Дейкстры "эффективнее", чем алгоритм Беллмана-Форда. Но при каких обстоятельствах алгоритм Беллмана-Форда лучше алгоритма Дейкстры?

Я знаю, что "лучше" - это широкое утверждение, поэтому конкретно я имею в виду в терминах скорости, а также пространства, если это применимо. Наверняка есть какая-то ситуация, в которой подход Беллмана-Форда лучше, чем подход Дейкстры.

Алгоритм Беллмана-Форда - это алгоритм кратчайшего пути с одним источником, поэтому при отрицательном весе ребра он может обнаружить отрицательные циклы в графе.

Единственное различие между ними заключается в том, что алгоритм Беллмана-Форда способен работать с отрицательными весами, в то время как алгоритм Дейкстры может работать только с положительными.

  • количество вершин в графе. В каждом из этих повторений, количество вершин с правильно вычисленными расстояниями растет, от из чего следует, что в конечном итоге все вершины будут иметь правильные > расстояния. расстояния. Этот метод позволяет применить алгоритм Беллмана-Форда > к более широкому кругу задач. к более широкому классу входов, чем алгоритм Дейкстры.

Однако алгоритм Дейкстры обычно считается лучшим при отсутствии ребер с отрицательным весом, так как типичная реализация двоичной очереди приоритетов имеет временную сложность O((|E|+|V|)log|V|) [очередь приоритетов кучи Фибоначчи дает O(|V|log|V| + |E|)], в то время как алгоритм Беллмана-Форда имеет сложность O(|V||E|).

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

Эффективной альтернативой Bellman-ford является Directed Acyclic Graph (DAG), который использует топологическую сортировку.

Как уже было сказано в выбранном ответа, Беллмана-Форда выполняет проверку на все вершины, Дейкстра только на один с лучшими расстояние до сих пор рассчитывается. Снова уже отмечалось, это повышает сложность подхода Дейкстры, однако он требует, чтобы сравнить все узлы, чтобы найти минимальные значения расстояния. Это не надо в Беллмана-Форда, это проще реализовать в распределенной среде. Что's, почему он используется в дистанционно-векторных протоколов маршрутизации (например, протокол RIP и igrp), где используется в основном местная информация. Чтобы использовать Дейкстры в протоколах маршрутизации, вместо этого, надо сначала распределить всю топологию, и это происходит в состоянии протоколов, таких как OSPF и ISIS.

Алгоритм Дейкстры Дейкстра алгоритм не способен различать отрицательных Весов ребер цикла в графе или нет

1. По положительному фронту вес:- Дейкстры всегда ПАСС если всех Весов ребер в графе положительно 2. Негативные краю мас. и не -ве краю мас. цикл:- Дейкстры всегда ПАСС даже если у нас есть вес некоторым краям как негативным, но нет цикла/цикла в графе наличие отрицательных Весов ребер. [я.э нет отрицательных Весов ребер цикла присутствует] 3. Негативные краю мас. и -Ве краю мас. цикл:- Дейкстры мая зачет/незачет даже если у нас есть вес некоторым краям как негативный наряду с цикл/цикл в графе наличие отрицательных Весов ребер.

Есть 4 основных разницу между ними я знаю:-

сложность Беллмана времени о(ВЭ) и Дейкстры алгоритм работает за o(ElogV)в случае maxheap используется.

Беллман никак релаксации для N-1 раз и Дейкстры алгоритмическая только 1 раз.

Беллмана может обрабатывать отрицательные веса, но Дейкстры алгоритм может'т.

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

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

Сформулируем определения и задачу.
Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами). Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины.
Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из одного города в другой, проехав как можно меньший путь.

Считаем, что в графе n вершин и m рёбер.
Пойдём от простого к сложному.

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

Алгоритм Форда-Беллмана

Алгоритм Дейкстры

Алгоритм Дейкстры для разреженных графов


Делает то же самое, что и алгоритм Дейкстры, но за количество операций порядка m * log(n). Следует заметить, что m может быть порядка n^2, то есть эта вариация алгоритма Дейкстры не всегда быстрее классической, а только при маленьких m.
Что нам нужно в алгоритме Дейкстры? Нам нужно уметь находить по значению d минимальную вершину и уметь обновлять значение d в какой-то вершине. В классической реализации мы пользуемся простым массивом, находить минимальную по d вершину мы можем за порядка n операций, а обновлять — за 1 операцию. Воспользуемся двоичной кучей (во многих объектно-ориентированных языках она встроена). Куча поддерживает операции: добавить в кучу элемент (за порядка log(n) операций), найти минимальный элемент (за 1 операцию), удалить минимальный элемент (за порядка log(n) операций), где n — количество элементов в куче.
Создадим массив d[0… n — 1] (его значение то же самое, что и раньше) и кучу q. В куче будем хранить пары из номера вершины v и d[v] (сравниваться пары должны по d[v]). Также в куче могут быть фиктивные элементы. Так происходит, потому что значение d[v] обновляется, но мы не можем изменить его в куче. Поэтому в куче могут быть несколько элементов с одинаковым номером вершины, но с разным значением d (но всего вершин в куче будет не более m, я гарантирую это). Когда мы берём минимальное значение в куче, надо проверить, является ли этот элемент фиктивным. Для этого достаточно сравнить значение d в куче и реальное его значение. А ещё для записи графа вместо двоичного массива используем массив списков.
m раз добавляем элемент в кучу, получаем порядка m * log(n) операций.
Псевдокод:

Я изучал три, и я излагаю свои выводы из них ниже. Может ли кто-нибудь сказать мне, понял ли я их достаточно точно или нет? Спасибо.

алгоритм Дейкстры используется только тогда, когда у вас есть один источник, и вы хотите знать наименьший путь от одного узла к другому, но терпит неудачу в таких случаях, как этой

(это самый важный. Я имею в виду, это тот, в котором я меньше всего уверен:)

3.Bellman-Ford используется как Dijkstra, когда есть только один источник. Это может обрабатывать отрицательные веса и его работа такая же, как у Floyd-Warshall, за исключением одного источника, верно?

Если вам нужно посмотреть соответствующие алгоритмы (спасибо Википедии):

вы правы в первых двух вопросах и о цели Floyd-Warshall (поиск кратчайших путей между всеми парами), но не об отношениях между Bellman-Ford и Floyd-Warshall: оба алгоритма используют динамическое программирование для поиска кратчайшего пути, но FW не то же самое, что запуск BF от каждого начального узла до каждого другого узла.

в BF возникает вопрос: каков кратчайший путь от источника к цели, используя не более k шагов, и работает время O (EV). Если бы мы должны были запустить его на другой узел, время работы было бы O (EV^2).

в FW возникает вопрос: каков кратчайший путь от i до j через k для всех узлов i, j,k. Это приводит к O (V^3) времени работы - лучше, чем BF для каждого начального узла (в разы до |V| для плотных графов).

еще одно замечание о отрицательных циклах / весах: Dijkstra может просто не дать правильных результатов. BF и FW не подведут - они будут правильно заявите, что нет минимального пути веса, так как отрицательный вес неограничен.

один источник кратчайших путей:

алгоритм Дейкстры-отрицательный вес не допускается-O(E+Vlg (V))

алгоритм Bellman ford-отрицательный вес разрешен. Но если отрицательный цикл присутствует, Bellman ford обнаружит-ve cycle-O(VE)

направленный ациклический граф - как следует из названия, он работает только для DAG-O(V+E)

все пары кратчайших путей:

алгоритм Дейкстры - отрицательный вес не допускается-O(VE + V^2lg (V))

алгоритм Беллмана Форда-O (V^2E)

метод умножения матричной цепи-сложность такая же, как алгоритм Беллмана Форда

для Floyd Warshall метода динамического программирования - сложность o(П^3)




Задача: Дан граф и начальная вершина src в графе, необходимо найти кратчайшие пути от src до всех вершин в данном графе. В графе могут присутствовать ребра с отрицательными весами.

Мы уже обсуждали алгоритм Дейкстры в качестве способа решения этой задачи. Алгоритм Дейкстры является жадным алгоритмом, а его сложность равна O(VLogV) (с использованием кучи Фибоначчи). Однако Дейкстра не работает для графов с отрицательными весами ребер, тогда как Беллман-Форд — вполне. Алгоритм Беллмана-Форда даже проще, чем алгоритм Дейкстры, и хорошо подходит для распределенных систем. В то же время сложность его равна O(VE), что больше, чем показатель для алгоритма Дейкстры.

Рекомендация: Прежде, чем двигаться к просмотру решения, попробуйте попрактиковаться самостоятельно.

Алгоритм

Ниже приведены подробно расписанные шаги.

  1. На этом шаге инициализируются расстояния от исходной вершины до всех остальных вершин, как бесконечные, а расстояние до самого src принимается равным 0. Создается массив dist[] размера |V| со всеми значениями равными бесконечности, за исключением элемента dist[src] , где src — исходная вершина.
  2. Вторым шагом вычисляются самые короткие расстояния. Следующие шаги нужно выполнять |V| -1 раз, где |V| — число вершин в данном графе.
    • Произведите следующее действие для каждого ребра u-v:
      Если dist[v] > dist[u] + вес ребра uv , то обновите dist[v]
      dist [v] = dist [u] + вес ребра uv
  3. На этом шаге сообщается, присутствует ли в графе цикл отрицательного веса. Для каждого ребра u-v необходимо выполнить следующее:

  • Если dist[v] > dist[u] + вес ребра uv , то в графе присутствует цикл отрицательного веса.

Как это работает? Как и в других задачах динамического программирования, алгоритм вычисляет кратчайшие пути снизу вверх. Сначала он вычисляет самые короткие расстояния, то есть пути длиной не более, чем в одно ребро. Затем он вычисляет кратчайшие пути длиной не более двух ребер и так далее. После i-й итерации внешнего цикла вычисляются кратчайшие пути длиной не более i ребер. В любом простом пути может быть максимум |V|-1 ребер, поэтому внешний цикл выполняется именно |V|-1 раз. Идея заключается в том, что если мы вычислили кратчайший путь с не более чем i ребрами, то итерация по всем ребрам гарантирует получение кратчайшего пути с не более чем i + 1 ребрами (доказательство довольно простое, вы можете сослаться на эту лекцию или видеолекцию от MIT)

Пример

Давайте разберемся в алгоритме на следующем примере графа. Изображения взяты отсюда.
Пусть начальная вершина равна 0. Примите все расстояния за бесконечные, кроме расстояния до самой src . Общее число вершин в графе равно 5, поэтому все ребра нужно пройти 4 раза.


Пусть ребра отрабатываются в следующем порядке: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D). Мы получаем следующие расстояния, когда проход по ребрам был совершен первый раз. Первая строка показывает начальные расстояния, вторая строка показывает расстояния, когда ребра (B, E), (D, B), (B, D) и (A, B) обрабатываются. Третья строка показывает расстояние при обработке (A, C). Четвертая строка показывает, что происходит, когда обрабатываются (D, C), (B, C) и (E, D).


Первая итерация гарантирует, что все самые короткие пути будут не длиннее пути в 1 ребро. Мы получаем следующие расстояния, когда будет совершен второй проход по всем ребрам (в последней строке показаны конечные значения).


Вторая итерация гарантирует, что все кратчайшие пути будут иметь длину не более 2 ребер. Алгоритм проходит по всем ребрам еще 2 раза. Расстояния минимизируются после второй итерации, поэтому третья и четвертая итерации не обновляют значения расстояний.


Выходные значения:

Читайте также: