Алгоритм беллмана форда и дейкстры отличия
Добавил пользователь Владимир З. Обновлено: 04.10.2024
Наглядное объяснение алгоритма Беллмана-Форда
Перед началом статьи хочу сказать, что еще больше полезной и нужной информации вы найдете в нашем Telegram-канале. Канал уже очень близок к отметке в 1000 подписчиков, сможем устроить новогодний подарок? Подпишитесь, мне будет очень приятно.
Алгоритм Беллмана-Форда находит в ориентированном графе кратчайшие пути от исходной вершины до всех остальных. В отличие от алгоритма Дейкстры, в алгоритме Беллмана-Форда могут быть рёбра с отрицательным весом.
Начнём с того, что все исходящие ребра записываются в таблице в алфавитном порядке.
Как и в алгоритме Дейкстры, создаётся таблица, в которой записывается расстояние до каждой вершины и предыдущая вершина. Расстояния для всех вершин, кроме исходной, инициализируются значением бесконечности. Расстояние обозначено переменной d, а предыдущая вершина — переменной π.
Алгоритм Беллмана-Форда проходит итеративный путь через все рёбра. Всего рёбер 9, поэтому путь этот будет насчитывать до 9 итераций. Во время каждой итерации какое-то одно ребро ослабляется. Во время первой итерации при переходе из вершины A в вершину C вес соответствующего ребра АС составляет -3. Текущее расстояние от исходной вершины до А равно бесконечности. При добавлении -3 к бесконечности результатом будет бесконечность, поэтому значение C будет равно бесконечности. Аналогично, при переходе от А до Е вес соответствующего ребра АЕ составляет 2. Но, так как расстояние до А бесконечно, значение Е будет равно бесконечности. То же верно и в отношении рёбер BF, CB, CH, FG, GB и HD. Все они дают один и тот же результат — бесконечность. И только последнее ребро, SA, даёт другой результат. Вес ребра SA равен 5. Текущее расстояние до S равно 0, поэтому расстояние от S до A составит 0 + 5 = 5. Вершина, предыдущая по отношению к вершине A, — это вершина S. После первой итерации алгоритм Беллмана-Форда нашёл путь от S до А.
Так как все рёбра были ослаблены, алгоритм начинает вторую итерацию. Нам важны рёбра, отходящие от S и A, поскольку расстояние до этих вершин уже известно. Расстояние до всех остальных вершин равно бесконечности. Обращаясь к таблице, содержащей рёбра, мы начинаем с ослабления ребра АС.
Вес ребра АС равен -3. Текущее расстояние до вершины А равно 5 (через ребро SA), поэтому расстояние до вершины С составит 5 + (-3) = 2. Вершина-предшественница С — это вершина А. Вес ребра АЕ равен 2. Расстояние до E составит 5 + 2 = 7 (через ребро SA). Вершиной, предыдущей по отношению к вершине E, становится теперь вершина A. Ребро BF пока ещё не может быть ослаблено.
Ребро CB может быть ослаблено, так как мы знаем расстояние до C. Расстояние до B составит 2 + 7 = 9, а вершина, предыдущая по отношению к вершине В, — это вершина C. Ребро CH может быть ослаблено, так как мы знаем расстояние до C. Расстояние до H составит 2 + (-3) = -1, а вершина-предшественница Н — это вершина C.
Ребро FG ещё не может быть ослаблено. Ребро GВ тоже не может быть ослаблено. А вот ребро HD можно ослабить, так как мы знаем, что расстояние до вершины H равно -1. Расстояние до вершины D составит -1 + 1 = 0, а вершина, предыдущая по отношению к вершине D, — это вершина H.
Расстояние до A от ребра SA уже посчитано и равно 5, так что никаких обновлений здесь не требуется. На этом заканчивается итерация 2.
Алгоритм Дейкстры
Поиск в орграфе кратчайших путей от одной вершины до всех остальных при неотрицательных ребрах.
Каждой вершине из множества вершин Vсопоставим метку — минимальное известное расстояние от этой вершины доa. Алгоритм на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа завершается, когда все вершины посещены.
Инициализация. Метка вершины aполагается = 0, метки остальных — бесконечности (т.е. расстояния отaпока неизвестны, и они помечаются как непосещённые)
В цикле по всем вершинам идет поиск «минимальной » вершины и релаксация из нее всех достижимых из нее вершин с сохранением результата.
Алгоритм Беллмана–Форда
Алгоритм Беллмана–Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана–Форда допускает рёбра с отрицательным весом.
Алгоритм носит имя двух американских учёных: Ричарда Беллмана (Richard Bellman) и Лестера Форда (Lester Ford). Форд фактически изобрёл этот алгоритм в 1956 г. при изучении другой математической задачи, подзадача которой свелась к поиску кратчайшего пути в графе, и Форд дал набросок решающего эту задачу алгоритма. Беллман в 1958 г. опубликовал статью, посвящённую конкретно задаче нахождения кратчайшего пути, и в этой статье он чётко сформулировал алгоритм в том виде, в котором он известен нам сейчас.
Алгоритм маршрутизации RIP (алгоритм Беллмана–Форда) был впервые разработан в 1969 году, как основной для сети ARPANET.
Дан ор. или неор. граф G со взвешенными рёбрами. Длина пути - сумма весов рёбер, входящих в этот путь. Найти кратчайшие пути от выделенной вершины sдо всех вершин графа (их м. не существовать, т.к., в графе, содерж. цикл с отрицат. суммарным весом, существует сколь угодно короткий путь от одной вершины этого цикла до другой) Цикл, сумма весов рёбер которого отрицательна, называется отрицательным циклом.
А. Б.–Ф. позволяет оч. просто определить, существует ли в графе G отрицательный цикл, достижимый из вершины s. Достаточно произвести внешнюю итерацию цикла не | V | − 1, a ровно |V| раз. Если при исполнении последней итерации длина кратчайшего пути до к.-л. В-ы строго уменьшилась, то в графе есть отрицат. цикл, достижимый изs. На основе этого м. предложить след. Оптимизацию: отслеживать изменения в графе и, как только они закончатся, дальнейшие итерации будут бессмысленны. Значит м. сделать выход из цикла.
Решение задачи на графе без отрицательных циклов
Для нахождения кратчайших путей от одной вершины до всех остальных, восп-ся методом динамического программирования. На входе - матрица Aij, содержащая длина дуг (ребер) между смежными вершинами. На выходе – вектор с кратчайшими расстояниями от выбранной вершины до всех остальных и указание об отсутствии отрицательных циклов.
1 2 3 4 5 0 6 ∞ 7 ∞
1 ∞ 6 ∞ 7 ∞ от 1 1 0 6 4 7 2
2 ∞ ∞ 1 8 -4 от след. 2 (от 2-й и 4-й) 0 2 4 7 -2
3 ∞ -2 ∞ ∞ ∞ 3 0 2 4 7 -2
Ребра перебираются по порядку
1) (2 - 3) (2 - 4) (2 - 5) (4 - 3) (4 - 5)
2) (3 - 2) (2 - 4) (2 – 5) (4 - 3) (4 - 5)
3) (5 - 3) (5 - 1) (1 - 2) (1 - 4)
Похоже на поиск в ширину от всех смежных вершин
Для заданного взвешенного ориентированного графа G= (V, Е) с истокомSи весовой функциейw: Е —»Rалгоритм Беллмана-Форда возвращает лог. значение, указыв., содержится ли в графе цикл с отрицат. весом, достижимый из истока. Если такой цикл существует, в алгоритме указывается, что решения не существует. Если же таких циклов нет, алгоритм выдает кратчайшие пути и их вес.
Procedure Bellman_Ford (G,w,S) - алгоритм Беллмана –Форда O(VE)
Initz (G,S) инициализируем граф
For i 1 to |V[G]| - 1 для всех вершин, кроме S
Do For каждого ребра (u,v) E|G|
Do Relax(u,v,w) релаксируем каждое ребро
For каждого ребра (u,v) E|G| проверяем нет ли отрицат цикла
Do If D[v] > D[u]+ w(u,v) Then Return False отрицательный цикл
В целом, а. Дейкстры, по сравнению с а. Беллмана-Форда, обеспечивает более реальную оценку ситуации в сети, более быструю реакцию на важные изменения в сети (такие, как включение новой линии связи) и уменьшает зацикливание пакетов; однако а. Дейкстры сложнее в реализации и требует в несколько раз больше памяти.
Алгоритм Беллмана — Форда.
История алгоритма связана сразу с тремя независимыми математиками: Лестером Фордом, Ричардом Беллманом и Эдвардом Муром. Форд и Беллман опубликовали алгоритм в 1956 и 1958 годах соответственно, а Мур сделал это в 1957 году. И иногда его называют алгоритмом Беллмана – Форда – Мура. Метод используется в некоторых протоколах дистанционно-векторной маршрутизации, например в RIP (Routing Information Protocol – Протокол маршрутной информации).
Также как и алгоритм Дейкстры, алгоритм Беллмана — Форда вычисляет во взвешенном графе кратчайшие пути от одной вершины до всех остальных. Он подходит для работы с графами, имеющими ребра с отрицательным весом. Но спектр применимости алгоритма затрагивает не все такие графы, ввиду того, что каждый очередной проход по пути, составленному из ребер, сумма весов которых отрицательна (т. е. по отрицательному циклу), лишь улучшает требуемое значение. Бесконечное число улучшений делает невозможным определение одного конкретного значения, являющегося оптимальным. В связи с этим алгоритм Беллмана — Форда не применим к графам, имеющим отрицательные циклы, но он позволяет определить наличие таковых, о чем будет сказано позже.
Решить задачу, т. е. найти все кратчайшие пути из вершины s до всех остальных, используя алгоритм Беллмана — Форда, это значит воспользоваться методом динамического программирования: разбить ее на типовые подзадачи, найти решение последним, покончив тем самым с основной задачей. Здесь решением каждой из таких подзадач является определение наилучшего пути от одного отдельно взятого ребра, до какого-либо другого.
Для хранения результатов работы алгоритма заведем одномерный массив d[]. В каждом его i-ом элементе будет храниться значение кратчайшего пути из вершины s до вершины i (если таковое имеется). Изначально, присвоим элементам массива d[] значения равные условной бесконечности (например, число заведомо большее суммы всех весов), а в элемент d[s] запишем нуль.
Так мы задействовали известную и необходимую информацию, а именно известно, что наилучший путь из вершины s в нее же саму равен 0, и необходимо предположить недоступность других вершин из s. По мере выполнения алгоритма, для некоторых из них, это условие окажется ложным, и вычисляться оптимальные стоимости путей до этих вершин из s.
Задан граф G=(V, E), n=|V|, а m=|E|. Обозначим смежные вершины этого графа символами v и u (vÎV и uÎV), а вес ребра (v, u) символом w. Иначе говоря, вес ребра, выходящего из вершины v и входящего в вершину u, будет равен w.
Тогда ключевая часть алгоритма Беллмана — Форда примет следующий вид:
На каждом n-ом шаге осуществляются попытки улучшить значения элементов массива d[]: если сумма, составленная из веса ребра w(v, u) и веса хранящегося в элементе d[v], меньше веса d[u], то она присваивается последнему.
Понимание краевой релаксации для алгоритма Дейкстры и алгоритма Беллмана-Форда
Целькратчайший путьнайти кратчайший путь от начальной вершины до вершины цели. Мы широко используем алгоритмы для решения проблемы кратчайших путей от конкурентного программирования до поиска направлений в Google Картах. Поняв ключевое понятие «расслабление края”, Действительно легче понять конкретные алгоритмы, скажем алгоритм Дийсктры или алгоритм Беллмана-Форда. Другими словами, может быть трудно сделать эти алгоритмы своими, не понимая ослабления границ. В этом посте я сосредоточусь на релаксации ребер и объясню общую структуру для решения проблемы кратчайших путей. Кроме того, мы рассмотрим простой алгоритм и его реализацию для лучшего понимания. Я использую Python для реализации. Этот пост структурирован следующим образом:
- В чем проблема кратчайших путей?
- Что такое крайнее расслабление?
- Порядок релаксации
- Кратчайший путь по DAG и его реализация
Обратите внимание, что мы не рассматриваем алгоритм Дейкстры или алгоритм Беллмана-Форда.
1. В чем проблема кратчайших путей?
В этом посте я объясняюпроблемы кратчайших путей из одного источникаиз задач кратчайших путей, в которых нам нужно найти все пути от одной начальной вершины до всех других вершин. Я определяю кратчайшие пути как наименьший взвешенный путь от начальной вершины до целевой вершины из всех других путей в взвешенном графе. Здесь вы можете думать, что «взвешенный» на взвешенном пути означает стоимость достижения вершины цели (некоторой вершины). С этого момента, когда я говорю просто график, это означает взвешенный график.
На графике ниже давайте подумаем о кратчайших путях от начальной вершины S до других вершин A и B.
Кратчайший путь от вершины S к вершине A становится «S → A». На приведенном выше графике есть единственный путь от вершины S до вершины A, поэтому нам не нужно заботиться о весах. С другой стороны, мы можем найти два пути от вершины S до вершины B, которые являются «S → B» и «S → A → B», и кратчайший путь становится «S → A → B». В «S → B» вес пути равен 3, но в «S → A → B» вес пути становится равным 2, и он самый короткий: 1 + 1 = 2. Мы можем рассматривать вес кратчайшего пути как кратчайшее расстояние от начальной вершины до одной вершины.
2. Что такое краевая релаксация?
Здесь я объясню важное и обычно используемое понятие релаксации краев для решения проблемы кратчайших путей. Как правило, вы можете решить все проблемы кратчайших путей с помощью рельефа. Релаксация края - это операция для расчета стоимости достижения вершины ниже. Конкретнее, операция станет:
ВершиныUа такжеvстоять соседей в графе иd[U] а такжеd[v] выдержать стоимость достижения вершинUа такжеvсоответственно. Также,вес(U,v) стоит вес ребра от вершиныUв вершинуv, Подводя итог, мы можем сделать этот рисунок ниже.
Теперь мы знаем, что можем достичь вершиныUот начальной вершины S через две вершины, и этот путь стоитd[U]. Также мы можем добраться до вершиныvот начальной вершины S до четырех вершин, и этот путь стоитd[v].
Здесь, крайние обновления релаксацииd[v] кd[U] +вес(U,v) когдаd[U] +вес(U,v) меньше чемd[v]. Другими словами, он обновляет текущую стоимость достижения вершиныv(d[v]) к более низкой стоимости достижения (d[U] +вес(U,v)). Причина, по которой он обновляет стоимость, состоит в том, что путь через вершинуUможет быть короче, потому что стоимость достижения пути через вершинуUбудет ниже, чем стоимость текущего пути. На самом деле,алгоритмы для задачи о кратчайших путях решают проблему путем многократного использования краевой релаксации,
Я покажу пример того, как мы можем решить проблему кратчайших путей, многократно используя граничную релаксацию. Давайте найдем кратчайшие пути для того же графа, что и раньше, с помощью релаксации ребер. Я предполагаю начальную вершину S и применяю релаксацию ребер к графу, чтобы получить кратчайшие пути к вершинам A и B.
Чтобы применить ослабление ребер, нам нужно знать стоимость достижения, но нет способа узнать это до поиска, поэтому мы инициализируем затраты достижения для вершин A и B как бесконечность (∞). Стоимость бесконечности для вершины означает, что мы не можем достичь этой вершины. С другой стороны, стоимость достижения от начальной вершины до начальной вершины равна нулю, поэтому мы устанавливаемdзначение вершины S как 0.
Сначала мы выбираем и ослабляем ребра, выходящие из вершины S, затем ребро, выходящие из вершины A. Прежде всего, применяем ослабление ребер к ребру SA.
Край СА удовлетворяетd[S] +вес(S, A) <d[A], мы устанавливаемd[A] какd[S] +вес(S, A) = 1. Здесь Π [A] обозначает вершину, достигающую перед вершиной A на пути достижения стоимостиd[А]. В этом случае Π [A] равно S. Π [A] = S означает путь достижения стоимостиd[A] всегда использует подпуть, A ← S. Подробности будут описаны ниже, но мы можем восстановить путь с помощью Π.
Мы расслабляем край SB таким же образом.
Ребро SB удовлетворяетd[S] +вес(S, B) <d[B], поэтому мы установилиd[B] какd[S] +вес(S, B) = 3. Дляd[B] восстановление пути, мы устанавливаем Π [B] как S. Затем мы ослабляем ребро AB, выходящее из вершины A.
Ребро AB удовлетворяетd[А] +вес(A, B) <d[B], поэтому мы установилиd[B] какd[А] +вес(А, В) = 2. Как только мы обновимdзначение B, мы также обновляем Π [B] как A. Из рисунка выше, вы можете найти, что кратчайшие расстояния от вершины S до вершин A и B равны стоимости достиженияd, Мы не можем обновитьdЗначение ниже, поэтому мы заканчиваем релаксацию края.
Здесь давайте подтвердим, что мы можем восстановить кратчайший путь, используя Π [A] = S и Π [B] = A. На приведенном выше графике мы собираемся реконструировать кратчайший путь от вершины S до вершины B в качестве примера. Из Π [B] = A мы можем знать, что должны посетить вершину A, прежде чем достигнуть вершины B на пути к вершине B. Из Π [A] = S мы можем знать, что мы должны сначала посетить вершину S, а затем достичь вершины. A. Вершина S является начальной вершиной, поэтому мы больше не можем двигаться назад. Обращая вершины, которые мы получили до сих пор, мы можем получить кратчайший путь от вершины S к вершине B, “S → A → B”. Как правило, мы можем восстановить кратчайший путь для вершиныvпутем отслеживания Π [v], Π [Π [v]], Π [Π [Π [v]]],… И реверсирование полученных вершин.
3. Порядок релаксации
В предыдущем разделе мы не заботились о порядке ослабления краев, но как нам решить порядок? Или мы действительно заботимся об этом? Кажется, что мы можем получить кратчайший путь случайным образом расслабляющими ребрами. Это не правильно, хотя. Здесь я объясню причину, почему мы должны заботиться о порядке и как выбрать край для отдыха.
По правде говоря, действительно плохой случай в эффективности вычислений существует, если вы выбираете и ослабляете границу случайным образом. Например, давайте подумаем о следующем графике. Я предполагаюdЗначения на этом графике уже инициализированы.
Во-первых, давайте расслабим края прямой линии слева направо.
Далее мы расслабляем край EG.
Затем мы расслабляем край СЕ.
Здесь вы можете обнаружить, что мы можем снова расслабить край EG.
Кроме того, когда мы ослабляем ребро AC, мы можем снова расслабить ребра CE и EG. Поэтому, если мы не будем обращать внимание на порядок, мы бы снова и снова ослабляли один и тот же край. В приведенном выше примере мы можем эффективно ослабить края, если ослабим их слева направо. Однако есть слишком плотные графики для визуализации, как в примере выше. Поэтому кажется нереальным найти эффективный заказ заранее. Это причина, почему мы должны заботиться о расслабляющем порядке.
Ну как надо выбирать и расслаблять края. Фактически, алгоритмы кратчайших путей, такие как алгоритм Дейкстры или алгоритм Беллмана-Форда, дают нам расслабляющий порядок. Что это значиткаждый алгоритм кратчайших путей в основном повторяет ослабление ребер и создает расслабляющий порядок в зависимости от характера графа(положительные или отрицательные веса, DAG, . и т. д.). Другими словами, мы должны искать способ выбора и расслабления краев, наблюдая за характером графика. Таким образом, каждый алгоритм кратчайших путей имеет следующую общую структуру:
4. Кратчайший путь по DAG и его реализация
В предыдущем разделе я сказал, что мы должны выбрать способ релаксации краев, наблюдая за характером графика. Здесь я объясню простой и легкий алгоритм кратчайших путей для DAG (Направленный ациклический граф) с реализацией Python. ДАГ это график не имеет циклического. В этом разделе я объясню алгоритм, как вы знаететопологический порядок.Если вы не знакомы с этим, проверьте мою статью:Понимание поиска в глубину и топологической сортировки с Python?
В алгоритме кратчайших путей на DAG мы можем получить кратчайшие пути, выбирая и ослабляя исходящие ребра в топологическом порядке. Это конкретный алгоритм следующим образом:
Давайте посмотрим, как работает алгоритм. Я показываю график, который я инициализировалdи топологически отсортированы следующим образом. Я предполагаю, что начальная вершина - B. Давайте попробуем решить проблему кратчайших путей.
Каждая вершина отсортирована по топологии, поэтому мы просто ослабляем исходящие ребра слева направо. Мы не можем ослабить выходящий край из самой левой вершины А, поэтому мы не обновляемd,
Затем мы ослабляем исходящие ребра из вершины B, то есть BC и BD. Как только мы ослабим края, мы обновляем Π. Мы устанавливаем Π [C] как B и Π [D] как B
Затем мы ослабляем исходящие ребра из вершины C. Мы не можем ослабить выходящие ребра до вершины D, поэтому мы только обновляемd[E] иd[F]. Кроме того, мы обновляем Π [E] как C, Π [F] как C.
Мы обновляем исходящий край из вершины D. Мы только обновляемd[E] и Π [E] как D.
Мы обновляем выходящий край из вершины E. Мы также обновляем Π [F] как E.
От вершины F нет выходящего ребра. Завершаем релаксацию ребра. Наконец, мы получаем кратчайшие расстояния следующим образом: мы не проверяем, работает ли он здесь, но мы можем восстановить кратчайшие пути из Π.
Впоследствии, давайте реализуем алгоритм кратчайших путей на DAG в Python для лучшего понимания. Реализация приведена ниже: В этой реализации этот код решает проблему кратчайших путей на графе, использованном в приведенном выше объяснении. Этот код оцениваетdи Π решить проблему. Я предполагаю, что мы уже знали топологический порядок заранее.
Во-первых, давайте посмотрим, как выражается график и его веса. В приведенном выше коде график реализован следующим образом:
Соответствующий рисунок для графика ниже:
Например, когда мы смотрим на вершину C,график[‘C’] возвращает [‘D’, ‘E’, ‘F’], которые являются достижимыми соседями из вершины C. Таким образом, эти вершины образуют исходящие ребра из вершины C. Кроме того, вы обнаружите, чтовеса[U,v] соответствует весу ребраультрафиолетовый,
Далее, давайте посмотрим на роль каждой линииdag_shortest_pathполучить кратчайшие пути. Строки от 2 до 4 - это инициализация следующим образом:dначальной вершины как 0, остальные вершины как ∞. Кроме того, эти строки инициализируют Π, чтобы восстановить путь.
Линии от 9 до 12 соответствуют краевой релаксации.d_temp<d[v] в коде соответствуетd[U] +вес(U,v) <d[v] в состоянии краевой релаксации. Когда это условие выполнено, оно обновляетd[v]. Как только он обновляетdтакже обновляет Π.
Код повторяет этот процесс для исходящих ребер из каждой вершины в топологическом порядке. Этот повторяющийся процесс отрабатывается двумя циклами for.torderсодержит вершины в топологическом порядке. Так жеграфиквозвращает вершины для построения исходящих ребер из вершины. Итак, мы получаем преимуществоультрафиолетовыйрассматривая вершину изtorderкакUиграфик[U] какv,
Это все для объяснения кода. Мы не проверяем результат, но вы можете выполнить код с помощью следующей команды в своем терминале: вы узнаете, что можете получитьdи Π правильно.
Наконец, давайте подумаем о временной сложности этого алгоритма. В этом алгоритме есть две основные вычислительные части. Один для топологической сортировки. Другой для расслабления края. В приведенном выше коде мы не делаем топологическую сортировку, но на самом деле нам нужно это сделать. Поэтому мы должны принять это во внимание. Мы можем выполнить топологическую сортировку с помощью поиска в глубину, поэтому сложность времениО(|В| + |Е|). Количество циклов влияет только на временную сложность релаксации ребер, поскольку процессы в цикле протекают в постоянном времени. Количество петель дляtorderэто |В| и количество петель дляграфик[U] это |Е|. Таким образом, временная сложность краевой релаксацииО(|В| + |Е|). Таким образом, вся временная сложность алгоритмаО(|В| + |Е|).
В этом посте я сосредоточусь на релаксации ребер и объясню проблему кратчайших путей и ее алгоритм. Когда вы понимаете ослабление фронта, вы можете легко понять алгоритм Дийсктра или алгоритм Беллмана-Форда. Также вы можете узнать разницу между этими алгоритмами. Спасибо за чтение моей статьи.
Алгоритм Беллмана
Содержание
История
Алгоритм маршрутизации RIP (алгоритм Беллмана–Форда) был впервые разработан в 1969 году, как основной для сети ARPANET.
Формулировка задачи
Дан ориентированный или неориентированный граф G со взвешенными рёбрами. Длиной пути назовём сумму весов рёбер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа.
Заметим, что кратчайших путей может не существовать. Так, в графе, содержащем цикл с отрицательным суммарным весом, существует сколь угодно короткий путь от одной вершины этого цикла до другой (каждый обход цикла уменьшает длину пути). Цикл, сумма весов рёбер которого отрицательна, называется отрицательным циклом.
Решение задачи на графе без отрицательных циклов
Решим поставленную задачу на графе, в котором заведомо нет отрицательных циклов.
Теперь рассмотрим все пути из s в i, содержащие ровно j рёбер. Каждый такой путь есть путь из alt="j-1" width="" height="" />
ребра, к которому добавлено последнее ребро. Если про пути длины alt="j-1" width="" height="" />
все данные уже подсчитаны, то определить j-й столбец матрицы не составляет труда.
Так выглядит алгоритм поиска длин кратчайших путей в графе без отрицательных циклов:
Внешний цикл выполняется раз, поскольку кратчайший путь не может содержать большее число ребер, иначе он будет содержать цикл, который точно можно выкинуть.
Вместо массива d можно хранить всю матрицу A, но это требует O(V²) памяти. Зато при этом можно вычислить и сами кратчайшие пути, а не только их длины. Для этого заведем матрицу Pij.
Если элемент Aij содержит длину кратчайшего пути из s в i, содержащего j рёбер, то Pij содержит предыдущую вершину до i в одном из таких кратчайших путей (ведь их может быть несколько).
Теперь алгоритм Беллмана–Форда выглядит так:
После выполнения этого алгоритма элементы " width="" height="" />
содержат длины кратчайших путей от s до i с количеством ребер j, и из всех таких путей следует выбрать самый короткий. А сам кратчайший путь до вершины i с j ребрами восстанавливается так:
Граф с отрицательными циклами
Алгоритм Беллмана–Форда позволяет очень просто определить, существует ли в графе G отрицательный цикл, достижимый из вершины s. Достаточно произвести внешнюю итерацию цикла не , a ровно |V| раз. Если при исполнении последней итерации длина кратчайшего пути до какой-либо вершины строго уменьшилась, то в графе есть отрицательный цикл, достижимый из s. На основе этого можно предложить следующую оптимизацию: отслеживать изменения в графе и, как только они закончатся, сделать выход из цикла (дальнейшие итерации будут бессмысленны).
Алгоритм Форда-Беллмана
Количество путей длины [math]k[/math] рёбер можно найти с помощью метода динамического программирования.
Пусть [math]d[k][u][/math] — количество путей длины [math]k[/math] рёбер, заканчивающихся в вершине [math]u[/math] . Тогда [math] d[k][u] = \sum\limits_
Аналогично посчитаем пути кратчайшей длины. Пусть [math]s[/math] — стартовая вершина. Тогда [math] d[k][u] = \min\limits_
Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования.
Также релаксацию можно свести к одномерному случаю, если не хранить длину пути в рёбрах. Одномерный массив будем обозначать [math]d'[/math] , тогда [math]d'[u] = \min(d'[u], \; d'[v] + \omega(vu))[/math]
Воспользуемся индукцией по [math]k[/math] :
База индукции
При [math]k = 0[/math] выполнено: [math]\rho(s, u) \leqslant +\infty \leqslant +\infty [/math]
Индукционный переход
Сначала докажем, что [math] \rho(s, u) \leqslant d'[u][/math] . Пусть после [math]k - 1 [/math] итерации выполняется [math]\rho(s, u) \leqslant d'[u] \leqslant \min\limits_
- [math]\min\limits_ d[i][u] = d[k+1][u][/math]
- [math]\min\limits_ d[i][u] = d[j][u] =\min\limits_ \; d[i][u][/math]
В этом алгоритме используется релаксация, в результате которой [math]d[v][/math] уменьшается до тех пор, пока не станет равным [math]\delta(s, v)[/math] . [math]d[v][/math] — оценка веса кратчайшего пути из вершины [math]s[/math] в каждую вершину [math]v \in V[/math] .
[math]\delta(s, v)[/math] — фактический вес кратчайшего пути из [math]s[/math] в вершину [math]v[/math] .
Рассмотрим произвольную вершину [math]v[/math] , достижимую из [math]s[/math] . Пусть [math]p = \langle v_0. v_
Докажем следующее утверждение:
После [math]n : (n \leqslant k)[/math] итераций первого цикла алгоритма, [math]d[v_n] = \delta(s, v_n) [/math]
Воспользуемся индукцией по [math]n[/math] :
База индукции
Перед первой итерацией утверждение очевидно выполнено: [math]d[v_0] = d[s] = \delta(s, s) = 0[/math]
Индукционный переход
Пусть граф [math] G [/math] не содержит отрицательных циклов, достижимых из вершины [math] s [/math] .
Тогда если вершина [math] v [/math] достижима из [math] s [/math] , то по лемме [math] d[v] = \delta (s, v)[/math] . Если вершина [math] v [/math] не достижима из [math] s [/math] , то [math] d[v] = \delta (s, v) = \mathcal <1>[/math] из несуществования пути.
Теперь докажем, что алгоритм вернет значение [math] true [/math] .
После выполнения алгоритма верно, что для всех [math] (u, v) \in E, \ d[v] = \delta (s, v) \leqslant \delta (s, u) + \omega (u,v) = d[u] + \omega (u,v)[/math] , значит ни одна из проверок не вернет значения [math] false [/math] .
Пусть граф [math] G [/math] содержит отрицательный цикл [math] c =
Предположим, что алгоритм возвращает [math] true [/math] , тогда для [math] i = 1. k [/math] выполняется [math] d[v_] \leqslant d[v_
Просуммируем эти неравенства по всему циклу: [math]\sum\limits_
Из того, что [math] v_0 = v_
Инициализация занимает [math] \Theta (V) [/math] времени, каждый из [math] |V| - 1 [/math] проходов требует [math] \Theta (E) [/math] времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает [math]O(E)[/math] времени. Значит алгоритм Беллмана-Форда работает за [math]O(V E)[/math] времени.
Приведенная выше реализация позволяет определить наличие в графе цикла отрицательного веса. Чтобы найти сам цикл, достаточно хранить вершины, из которых производится релаксация.
Если после [math]|V| - 1[/math] итерации найдется вершина [math] v [/math] , расстояние до которой можно уменьшить, то эта вершина либо лежит на каком-нибудь цикле отрицательного веса, либо достижима из него. Чтобы найти вершину, которая лежит на цикле, можно [math]|V| - 1[/math] раз пройти назад по предкам из вершины [math] v [/math] . Так как наибольшая длина пути в графе из [math]|V|[/math] вершин равна [math]|V| - 1[/math] , то полученная вершина [math] u [/math] будет гарантированно лежать на отрицательном цикле.
Зная, что вершина [math] u [/math] лежит на цикле отрицательного веса, можно восстанавливать путь по сохраненным вершинам до тех пор, пока не встретится та же вершина [math] u [/math] . Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.
разница между алгоритмом Беллмана Форда и алгоритмом Дейкстры
В чем разница между прямым-обратным алгоритмом на n-граммовой модели и алгоритмом Витерби на скрытой марковской модели (HMM)? Когда я рассматриваю реализацию этих двух алгоритмов, единственное, что я обнаружил, - это то, что вероятность транзакции исходит из разных вероятностных моделей. Есть ли.
Я реализовал решение алгоритма Беллмана-Форда с очередью и сравнил его производительность с алгоритмом Дейкстры. Они были довольно близки, и это было для меня неожиданностью, потому что сложность Bellman - Ford-O(NM). Я знаю, что сложность - это наихудший случай, но все равно результат был.
Алгоритм Беллмана-Форда-это алгоритм кратчайшего пути с одним источником, который допускает отрицательный вес ребра и может обнаруживать отрицательные циклы в графике.
Алгоритм Дейкстры также является еще одним алгоритмом кратчайшего пути с одним источником. Однако вес всех ребер должен быть неотрицательным.
В вашем случае, что касается общей стоимости, разницы не будет, так как ребра в графике имеют неотрицательный вес. Однако обычно используется алгоритм Дейкстры, поскольку типичная реализация с двоичной кучей имеет Theta((|E|+|V|)log|V|) временную сложность, в то время как алгоритм Беллмана-Форда имеет O(|V||E|) сложность.
Если существует более 1 пути с минимальной стоимостью, фактический возвращаемый путь зависит от реализации (даже для одного и того же алгоритма).
Вершины в алгоритме Дейкстры содержат всю информацию о сети. Нет такой вещи, чтобы каждая вершина заботилась только о себе и своих соседях. С другой стороны, узлы алгоритма Беллмана-Форда содержат только ту информацию, которая связана с. Эта информация позволяет этому узлу просто знать, к каким соседним узлам он может подключиться, и к узлу, из которого происходит связь, взаимно. Алгоритм Дейкстры быстрее, чем алгоритм Беллмана-Форда, однако второй алгоритм может быть более полезен для решения некоторых проблем, таких как отрицательные веса путей.
Алгоритм Джикстры-это жадный метод, в котором для реализации алгоритма Беллманфорда требуется динамический подход.
В djikstra algo мы выполняем релаксацию каждого узла/вершин в цикле, где, как и в bellmanford algo, мы выполняем релаксацию только|v-1| раз .
Алгоритм Дейкстры подходит для графа, когда его вес ребра положителен, и терпит неудачу в случае графа с отрицательными краями, где, как у алгоритма беллманфорда, есть преимущество перед djikstra, которое он может реализовать, даже если вес ребра отрицателен.
беллманфорд может найти, существует ли решение графа или нет (т. Е. Данный ориентированный граф имеет отрицательный весовой цикл или нет), где, как и алгоритм djikstra, не удается сделать то же самое.
временная сложность алгоритма djikstra составляет O(v^2) при реализации линейным массивом,O(e.log v)при реализации с помощью кучи binay или кучи Фибоначчи, где, как у алгоритма беллманфорда, временная сложность O(|v| |e|).
Как мы можем использовать алгоритм Дейкстры или Беллмана-Форда для поиска кратчайшего пути в графе, некоторые ребра которого затрагиваются, если мы идем по определенным вершинам? Таким образом, длина затронутого края будет больше или меньше исходной длины.
Может ли кто-нибудь уточнить, подпадает ли алгоритм Дейкстры под динамическое программирование или нет. Почему мы называем это алгоритмом Флойда уорсхолла, подпадающим под подход динамического программирования. Я не в состоянии понять разницу между ними. Когда я попытался сделать это, я.
Похожие вопросы:
В чем разница между алгоритмом онлайн-сортировки и алгоритмом внешней сортировки ? Они одинаковые или разные?
Поэтому если я пытаюсь найти кратчайший путь с помощью алгоритма Беллмана Форда, то использую этот метод для проверки наличия пути: public boolean hasPath(int v)< return distTo[v] <.
Мне было интересно, в чем разница между поиском по равномерной стоимости и алгоритмом Дейкстры . Похоже, это один и тот же алгоритм.
В чем разница между прямым-обратным алгоритмом на n-граммовой модели и алгоритмом Витерби на скрытой марковской модели (HMM)? Когда я рассматриваю реализацию этих двух алгоритмов, единственное, что.
Я реализовал решение алгоритма Беллмана-Форда с очередью и сравнил его производительность с алгоритмом Дейкстры. Они были довольно близки, и это было для меня неожиданностью, потому что сложность.
Как мы можем использовать алгоритм Дейкстры или Беллмана-Форда для поиска кратчайшего пути в графе, некоторые ребра которого затрагиваются, если мы идем по определенным вершинам? Таким образом.
Может ли кто-нибудь уточнить, подпадает ли алгоритм Дейкстры под динамическое программирование или нет. Почему мы называем это алгоритмом Флойда уорсхолла, подпадающим под подход динамического.
У меня просто есть одна путаница, которая заключается в том, что в случае Беллмана-Форда мы запускаем его n-1 раз, что не является ребрами, в то время как в алгоритме Флойда уорсхолла мы запускаем.
В чем точная разница между моделью и алгоритмом? Возьмем в качестве примера логистическую регрессию . Является ли логистическая регрессия моделью или алгоритмом и почему?
в настоящее время я понимаю, что алгоритм Дейкстры более эффективен, чем алгоритм Беллмана-Форда, только он не может обрабатывать отрицательные ребра. Однако скажем, что у нас есть реберный.
Алгоритм беллмана форда и дейкстры отличия
Алгоритм Беллмана–Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| ? |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана–Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.
Также как и алгоритм Дейкстры, алгоритм Беллмана — Форда вычисляет во взвешенном графе кратчайшие пути от одной вершины до всех остальных. Он подходит для работы с графами, имеющими ребра с отрицательным весом. Но спектр применимости алгоритма затрагивает не все такие графы, ввиду того, что каждый очередной проход по пути, составленному из ребер, сумма весов которых отрицательна (т. е. по отрицательному циклу), лишь улучшает требуемое значение. Бесконечное число улучшений делает невозможным определение одного конкретного значения, являющегося оптимальным. В связи с этим алгоритм Беллмана — Форда не применим к графам, имеющим отрицательные циклы, но он позволяет определить наличие таковых.
Решить задачу, т. е. найти все кратчайшие пути из вершины s до всех остальных, используя алгоритм Беллмана — Форда, это значит воспользоваться методом динамического программирования: разбить ее на типовые подзадачи, найти решение последним, покончив тем самым с основной задачей. Здесь решением каждой из таких подзадач является определение наилучшего пути от одного отдельно взятого ребра, до какого-либо другого. Для хранения результатов работы алгоритма заведем одномерный массив d[]. В каждом его i-ом элементе будет храниться значение кратчайшего пути из вершины s до вершины i (если таковое имеется). Изначально, присвоим элементам массива d[] значения равные условной бесконечности (например, число заведомо большее суммы всех весов), а в элемент d[s] запишем нуль. Так мы задействовали известную и необходимую информацию, а именно известно, что наилучший путь из вершины s в нее же саму равен 0, и необходимо предположить недоступность других вершин из s. По мере выполнения алгоритма, для некоторых из них, это условие окажется ложным, и вычисляться оптимальные стоимости путей до этих вершин из s(по материалам kvodo).
Алгоритм Беллмана – Форда | DP-23
Для данного графа и исходной вершины src в графе найдите кратчайшие пути от src ко всем вершинам данного графа. График может содержать отрицательные весовые ребра.
Мы обсудили алгоритм Дейкстры для этой задачи. Алгоритм Дейкстры является алгоритмом Гриди, а временная сложность равна O (VLogV) (с использованием кучи Фибоначчи). Дейкстра не работает для графов с отрицательными весовыми гранями, Беллман-Форд работает для таких графов. Bellman-Ford также проще, чем Dijkstra и хорошо подходит для распределенных систем. Но временная сложность Беллмана-Форда составляет O (VE), что больше, чем у Дейкстры.
Алгоритм
Ниже приведены подробные шаги.
2) Этот шаг рассчитывает кратчайшие расстояния. Выполните | V | -1 раз, где | V | количество вершин в данном графе.
… .. а) Делайте следующее для каждого края уф
……………… Если dist [v]> dist [u] + вес края uv, то обновите dist [v]
………………… .dist [v] = dist [u] + вес края уф
3) Этот шаг сообщает, есть ли отрицательный весовой цикл на графике. Делайте следующее для каждого края уф
…… Если dist [v]> dist [u] + вес ребра uv, то «График содержит отрицательный весовой цикл»
Идея шага 3 заключается в том, что шаг 2 гарантирует кратчайшие расстояния, если график не содержит отрицательный весовой цикл. Если мы повторим все ребра еще раз и получим более короткий путь для любой вершины, тогда будет отрицательный весовой цикл
пример
Давайте разберем алгоритм на следующем примере графа. Изображения взяты из этого источника.
Пусть заданная вершина источника равна 0. Инициализируйте все расстояния как бесконечные, кроме расстояния до самого источника. Общее количество вершин в графе 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 раза. Расстояния минимизируются после второй итерации, поэтому третья и четвертая итерации не обновляют расстояния.
Реализация:
// структура для представления взвешенного ребра в графе
int src, dest, weight;
// структура для представления связанных, направленных и
// взвешенный график
// V-> Количество вершин, E-> Количество ребер
// график представлен в виде массива ребер.
struct Edge* edge;
// Создаем граф с V вершинами и E ребрами
struct Graph* createGraph( int V, int E)
struct Graph* graph = new Graph;
graph->edge = new Edge[E];
// Утилита, используемая для печати решения
void printArr( int dist[], int n)
printf ( "Vertex Distance from Source\n" );
for ( int i = 0; i < n; ++i)
printf ( "%d \t\t %d\n" , i, dist[i]);
// Основная функция, которая находит кратчайшие расстояния от источника до
// все остальные вершины, использующие алгоритм Беллмана-Форда. Функция
// также обнаруживает отрицательный весовой цикл
void BellmanFord( struct Graph* graph, int src)
// Шаг 1: Инициализировать расстояния от src до всех остальных вершин
for ( int i = 0; i < V; i++)
// Шаг 2: ослабить все ребра | V | - 1 раз. Простой кратчайший
// путь от src до любой другой вершины может иметь самое большее | V | - 1
for ( int i = 1; i <= V - 1; i++) <
for ( int j = 0; j < E; j++) <
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
// Шаг 3: проверка циклов с отрицательным весом. Вышеуказанный шаг
// гарантирует кратчайшие расстояния, если граф не содержит
// отрицательный весовой цикл. Если мы получим более короткий путь, то там
for ( int i = 0; i < E; i++) <
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) <
printf ( "Graph contains negative weight cycle" );
return ; // Если обнаружен отрицательный цикл, просто вернемся
// Программа драйвера для проверки вышеуказанных функций
/ * Давайте создадим график, приведенный в примере выше * /
int V = 5; // Количество вершин в графе
int E = 8; // Количество ребер в графе
struct Graph* graph = createGraph(V, E);
// добавляем ребро 0-1 (или AB на рисунке выше)
// добавляем ребро 0-2 (или AC на рисунке выше)
// добавить ребро 1-2 (или BC на рисунке выше)
// добавляем ребро 1-3 (или BD на рисунке выше)
// добавить ребро 1-4 (или AE на рисунке выше)
// добавляем ребро 3-2 (или DC на рисунке выше)
// добавляем ребро 3-1 (или DB на рисунке выше)
// добавить ребро 4-3 (или ED на рисунке выше)
// Java-программа для кратчайшего пути Беллмана-Форда
// алгоритм.
// Класс для представления связного, ориентированного и взвешенного графа
// Класс для представления взвешенного ребра в графе
int src, dest, weight;
src = dest = weight = 0 ;
// Создаем граф с V вершинами и E ребрами
Graph( int v, int e)
edge = new Edge[e];
for ( int i = 0 ; i < e; ++i)
edge[i] = new Edge();
// Основная функция, которая находит кратчайшие расстояния от src
// ко всем остальным вершинам, используя алгоритм Беллмана-Форда.
// функция также обнаруживает отрицательный весовой цикл
void BellmanFord(Graph graph, int src)
int V = graph.V, E = graph.E;
int dist[] = new int [V];
// Шаг 1: Инициализировать расстояния от src до всех остальных
// вершины как БЕСКОНЕЧНЫЕ
for ( int i = 0 ; i < V; ++i)
// Шаг 2: ослабить все ребра | V | - 1 раз. Простой
// кратчайший путь от src до любой другой вершины
// иметь самое большее | V | - 1 ребро
for ( int i = 1 ; i < V; ++i) <
for ( int j = 0 ; j < E; ++j) <
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
// Шаг 3: проверка циклов с отрицательным весом. Над
// шаг гарантирует кратчайшие расстояния, если граф не
// содержат отрицательный весовой цикл. Если мы получим короче
// путь, то есть цикл.
for ( int j = 0 ; j < E; ++j) <
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) <
System.out.println( "Graph contains negative weight cycle" );
// Утилита, используемая для печати решения
void printArr( int dist[], int V)
System.out.println( "Vertex Distance from Source" );
for ( int i = 0 ; i < V; ++i)
System.out.println(i + "\t\t" + dist[i]);
// Метод драйвера для проверки вышеуказанной функции
public static void main(String[] args)
int V = 5 ; // Количество вершин в графе
int E = 8 ; // Количество ребер в графе
Graph graph = new Graph(V, E);
// добавляем ребро 0-1 (или AB на рисунке выше)
graph.edge[ 0 ].src = 0 ;
graph.edge[ 0 ].dest = 1 ;
graph.edge[ 0 ].weight = - 1 ;
// добавляем ребро 0-2 (или AC на рисунке выше)
graph.edge[ 1 ].src = 0 ;
graph.edge[ 1 ].dest = 2 ;
graph.edge[ 1 ].weight = 4 ;
// добавить ребро 1-2 (или BC на рисунке выше)
graph.edge[ 2 ].src = 1 ;
graph.edge[ 2 ].dest = 2 ;
graph.edge[ 2 ].weight = 3 ;
// добавляем ребро 1-3 (или BD на рисунке выше)
graph.edge[ 3 ].src = 1 ;
graph.edge[ 3 ].dest = 3 ;
graph.edge[ 3 ].weight = 2 ;
// добавить ребро 1-4 (или AE на рисунке выше)
graph.edge[ 4 ].src = 1 ;
graph.edge[ 4 ].dest = 4 ;
graph.edge[ 4 ].weight = 2 ;
// добавляем ребро 3-2 (или DC на рисунке выше)
graph.edge[ 5 ].src = 3 ;
graph.edge[ 5 ].dest = 2 ;
graph.edge[ 5 ].weight = 5 ;
// добавляем ребро 3-1 (или DB на рисунке выше)
graph.edge[ 6 ].src = 3 ;
graph.edge[ 6 ].dest = 1 ;
graph.edge[ 6 ].weight = 1 ;
// добавить ребро 4-3 (или ED на рисунке выше)
graph.edge[ 7 ].src = 4 ;
graph.edge[ 7 ].dest = 3 ;
graph.edge[ 7 ].weight = - 3 ;
from collections import defaultdict
def __init__( self , vertices):
def addEdge( self , u, v, w):
self .graph.append([u, v, w])
def printArr( self , dist):
print ( "Vertex Distance from Source" )
for i in range ( self .V):
print ( "% d \t\t % d" % (i, dist[i]))
def BellmanFord( self , src):
dist = [ float ( "Inf" )] * self .V
for i in range ( self .V - 1 ):
for u, v, w in self .graph:
if dist[u] ! = float ( "Inf" ) and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in self .graph:
if dist[u] ! = float ( "Inf" ) and dist[u] + w < dist[v]:
print "Graph contains negative weight cycle"
g.addEdge( 0 , 1 , - 1 )
g.addEdge( 0 , 2 , 4 )
g.addEdge( 1 , 2 , 3 )
g.addEdge( 1 , 3 , 2 )
g.addEdge( 1 , 4 , 2 )
g.addEdge( 3 , 2 , 5 )
g.addEdge( 3 , 1 , 1 )
g.addEdge( 4 , 3 , - 3 )
// Класс для представления связного, ориентированного и взвешенного графа
// Класс для представления взвешенного ребра в графе
public int src, dest, weight;
src = dest = weight = 0;
// Создаем граф с V вершинами и E ребрами
Graph( int v, int e)
edge = new Edge[e];
for ( int i = 0; i < e; ++i)
edge[i] = new Edge();
// Основная функция, которая находит кратчайшие расстояния от src
// ко всем остальным вершинам, используя алгоритм Беллмана-Форда.
// функция также обнаруживает отрицательный весовой цикл
void BellmanFord(Graph graph, int src)
int V = graph.V, E = graph.E;
int [] dist = new int [V];
// Шаг 1: Инициализировать расстояния от src до всех остальных
// вершины как БЕСКОНЕЧНЫЕ
for ( int i = 0; i < V; ++i)
dist[i] = int .MaxValue;
// Шаг 2: ослабить все ребра | V | - 1 раз. Простой
// кратчайший путь от src до любой другой вершины
// иметь самое большее | V | - 1 ребро
for ( int i = 1; i < V; ++i) <
for ( int j = 0; j < E; ++j) <
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != int .MaxValue && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
// Шаг 3: проверка циклов с отрицательным весом. Над
// шаг гарантирует кратчайшие расстояния, если граф не
// содержат отрицательный весовой цикл. Если мы получим короче
// путь, то есть цикл.
for ( int j = 0; j < E; ++j) <
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != int .MaxValue && dist[u] + weight < dist[v]) <
Console.WriteLine( "Graph contains negative weight cycle" );
// Утилита, используемая для печати решения
void printArr( int [] dist, int V)
Console.WriteLine( "Vertex Distance from Source" );
for ( int i = 0; i < V; ++i)
Console.WriteLine(i + "\t\t" + dist[i]);
// Метод драйвера для проверки вышеуказанной функции
public static void Main()
int V = 5; // Количество вершин в графе
int E = 8; // Количество ребер в графе
Graph graph = new Graph(V, E);
// добавляем ребро 0-1 (или AB на рисунке выше)
// добавляем ребро 0-2 (или AC на рисунке выше)
// добавить ребро 1-2 (или BC на рисунке выше)
// добавляем ребро 1-3 (или BD на рисунке выше)
// добавить ребро 1-4 (или AE на рисунке выше)
// добавляем ребро 3-2 (или DC на рисунке выше)
// добавляем ребро 3-1 (или DB на рисунке выше)
// добавить ребро 4-3 (или ED на рисунке выше)
// Этот код предоставлен Ryuga
Примечания
1) Отрицательные веса встречаются в различных приложениях графов. Например, вместо того, чтобы платить за путь, мы можем получить некоторое преимущество, если будем следовать по пути.
2) Беллман-Форд работает лучше (лучше, чем у Дейксры) для распределенных систем. В отличие от Дейксры, где нам нужно найти минимальное значение всех вершин, в Беллман-Форде ребра считаются один за другим.
Упражнение
1) Стандартный алгоритм Беллмана-Форда сообщает о кратчайшем пути, только если нет отрицательных циклов веса. Измените его так, чтобы он отображал минимальные расстояния, даже если есть отрицательный весовой цикл.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Читайте также: