Каково худшее время работы алгоритма беллмана форда на графе с n вершинами

Обновлено: 05.07.2024

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

1.2 Математическое описание алгоритма

Пусть задан граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math] и выделенной вершиной-источником [math]u[/math] . Обозначим через [math]d(v)[/math] кратчайшее расстояние от источника [math]u[/math] до вершины [math]v[/math] .

Алгоритм Беллмана-Форда ищет функцию [math]d(v)[/math] как единственное решение уравнения

с начальным условием [math]d(u) = 0[/math] .

1.3 Вычислительное ядро алгоритма

Основной операцией алгоритма является релаксация ребра: если [math]e = (w, v) \in E[/math] и [math]d(v) \gt d(w) + f(e)[/math] , то производится присваивание [math]d(v) \leftarrow d(w) + f(e)[/math] .

1.4 Макроструктура алгоритма

Алгоритм последовательно уточняет значения функции [math]d(v)[/math] .

В самом начале производится присваивание [math]d(u) = 0[/math] , [math]d(v) = \infty[/math] , [math]\forall v \ne u[/math] .
Далее происходит [math]|V|-1[/math] итерация, в ходе каждой из которых производится релаксация всех рёбер графа.

Структуру можно описать следующим образом:

1. Инициализация: всем вершинам присваивается предполагаемое расстояние [math]t(v)=\infty[/math] , кроме вершины-источника, для которой [math]t(u)=0[/math] .

2. Релаксация множества рёбер [math]E[/math]

а) Для каждого ребра [math]e=(v,z) \in E[/math] вычисляется новое предполагаемое расстояние [math]t^' (z)=t(v)+ w(e)[/math] .

б) Если [math]t^' (z)\lt t(z)[/math] , то происходит присваивание [math]t(z) := t' (z)[/math] (релаксация ребра [math]e[/math] ).

3. Алгоритм производит релаксацию всех рёбер графа до тех пор, пока на очередной итерации происходит релаксация хотя бы одного ребра.

Если на [math]|V|[/math] -й итерации всё ещё производилась релаксацию рёбер, то в графе присутствует цикл отрицательной длины. Ребро [math]e=(v,z)[/math] , лежащее на таком цикле, может быть найдено проверкой следующего условия (проверяется для всех рёбер за линейное время): [math]t(v)+w(e)\lt d(z)[/math]

1.5 Схема реализации последовательного алгоритма

Последовательный алгоритм реализуется следующим псевдокодом:

1.6 Последовательная сложность алгоритма

Алгоритм выполняет [math]|V|-1[/math] итерацию, на каждой из которых происходит релаксация [math]|E|[/math] рёбер. Таким образом, общий объём работы составляет [math]O(|V||E|)[/math] операций.

Константа в оценке сложности может быть уменьшена за счёт использования следующих двух стандартных приёмов.

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

1.7 Информационный граф

На рисунке 1 представлен информационный граф алгоритма, демонстрирующий описанные уровни параллелизма.

На приведенном далее информационном графе нижний уровень параллелизма обозначен в горизонтальных плоскостях. Множество всех плоскостей представляет собой верхний уровень параллелизма (операции в каждой плоскости могут выполняться параллельно).

Нижний уровень параллелизма на графе алгоритма расположен на уровнях [2] и [3], соответствующим операциям инициализации массива дистанций [2] и обновления массива c использованием данных массива ребер [3]. Операция [4] - проверка того, были ли изменения на последней итерации и выход из цикла, если таковых не было.

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

1.8 Ресурс параллелизма алгоритма

Алгоритм обладает значительным ресурсом параллелизма. Во-первых, поиск кратчайших путей от различных вершин может производиться независимо для каждой из вершин (параллельные вертикальные плоскости на рисунке 1). Во-вторых, поиск кратчайших путей от фиксированной вершины [math]u[/math] также может выполняться параллельно: инициализация начальных путей [2] требует [math]|V|[/math] параллельных операции, релаксация каждого ребра требует [math]O(|E|)[/math] параллельных операции.

Таким образом, при наличии [math]O(|E|)[/math] процессоров алгоритм завершит работу максимум за [math]|V|[/math] шагов. В реальности, шагов обычно требуется меньше, а именно [math]O(r)[/math] -(максимальная длина среди всех кратчайших путей от выбранной вершины-источника [math]u[/math] ).

Таким образом, ширина ярусно-параллельной формы алгоритма равна [math]O(|E|)[/math] , высота ЯПФ - [math]O(r) | r \lt |V|[/math] .

Алгоритм Δ-шагания может рассматриваться как параллельная версия алгоритма Беллмана-Форда.

Объём входных данных: [math]O(|V| + |E|)[/math] .

Выходные данные (возможные варианты):

для каждой вершины [math]v[/math] исходного графа – последнее ребро [math]e^*_v = (w, v)[/math] , лежащее на кратчайшем пути от вершины [math]u[/math] к [math]v[/math] , или соответствующая вершина [math]w[/math] ;
для каждой вершины [math]v[/math] исходного графа – суммарный вес [math]f^*(v)[/math] кратчайшего пути от от вершины [math]u[/math] к [math]v[/math] .

Объём выходных данных: [math]O(|V|)[/math] .

1.10 Свойства алгоритма

Алгоритм может распознавать наличие отрицательных циклов в графе. Ребро [math]e = (v, w)[/math] лежит на таком цикле, если вычисленные алгоритмом кратчайшие расстояния [math]d(v)[/math] удовлетворяют условию

[math] d(v) + f(e) \lt d(w), [/math]

где [math]f(e)[/math] – вес ребра [math]e[/math] . Условие может быть проверено для всех рёбер графа за время [math]O(|E|)[/math] .

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

История алгоритма связана сразу с тремя независимыми математиками: Лестером Фордом, Ричардом Беллманом и Эдвардом Муром. Форд и Беллман опубликовали алгоритм в 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], то она присваивается последнему.

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

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	21.02.2019
Размер файла	844,7 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Выполнил Анастасин В.

Алгоритм Форда-Беллмана - алгоритм поиска кратчайшего пути во взвешенном графе.

История алгоритма связана сразу с тремя независимыми математиками: Лестером Фордом, Ричардом Беллманом и Эдвардом Муром. Форд и Беллман опубликовали алгоритм в 1956 и 1958 годах соответственно, а Мур сделал это в 1957 году. И иногда его называют алгоритмом Беллмана - Форда - Мура. Метод используется в некоторых протоколах дистанционно-векторной маршрутизации, например в RIP (Routing Information Protocol - Протокол маршрутной информации).

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

В качестве среды разработки мною была выбрана среда Microsoft Visual Studio 2017, язык программирования - С++.

В ходе выполнения данной курсовой работы были приобретены навыки работы с формами и их элементами в среде Microsoft Visual Studio 2017, навыки работы с проектами и многомодульными программами.

Требуется разработать программу, которая находит кратчайший путь во взвешенном графе, используя алгоритм Форда-Беллмана.

Исходный граф в программе должен задаваться матрицей смежности, причём при вводе данных должны быть предусмотрены граничные условия, должна выполняться проверка корректности введенных данных. Устройства ввода данных - клавиатура и мышь. Программа должна быть разработана для работы в операционной системе Microsoft Windows. Для удобства использования программы должен быть разработан графический интерфейс оформленный в windows.forms с возможностью ввода и вывода информации.

Задания выполняются в соответствии с вариантом №2.

Общие теоретические сведения

Пусть нам дана матрица весов С(D) орграфа D и начальная вершина s. Найдем расстояния от вершины s до всех вершин орграфа D: D[v] = d(s,v), v О V.

1. Всем вершинам vОV орграфа присвоим метку D[v] = csv. Вершине s присвоим метку D[s] = 0.

3. Выберем произвольную вершину vО V \ .

4. Выберем произвольную вершину u ОV.

5. Положим D[v] = min (D[v], D[u] + cuv).

6. Если вершина u пробежала еще не все множество вершин V, то выбрать среди оставшихся произвольную вершину и вернуться к шагу 5.

7. Если вершина v пробежала еще не все множество вершин V \ ~~, то выбрать среди оставшихся произвольную вершину и перейти к шагу 4.~~

8. Если k < n-2, то положить k=k+1 и вернуться к шагу 3, иначе алгоритм заканчивает свою работу, полученные значения D[v] будут равны расстояниям d(s,v) в орграфе D.

Описание алгоритма программы

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

На рисунке 1 показана схема работы программы.

Рисунок 1 - Схема программы.

На Рисунке 2 показана схема работы алгоритма Форда-Беллмана.

Рисунок 2 - Схема Алгоритма Форда-Беллмана.

Ручной расчёт задачи

Определим минимальные пути из вершины v1 до всех остальных вершин в нагруженном орграфе D, изображенном на рис. 3.

Рисунок 3 - Орграф.

Ниже в таблице приведены матрица весов, а также все вычисления по шагам. Матрица весов изображена на рисунке 4.

Рисунок 4 - Матрица весов.

На первом шаге всем вершинам vV орграфа присвоим метку D[v] = csv, где s = v1. Выберем следующую вершину v2. Ей присвоим метку D[v2] = min (D[v2], D[u] + cuv), где u V, т.е. D[v2] = min (D[v2], D[v3]+ c32, D[v4]+ c42, D[v5]+ c52, D[v6]+ c62) = (,5+2, 5+2, 2+, 12+) = 7. Зафиксируем, что эта метка может быть получена из вершин 3 или 4.

Аналогично корректируются метки всех оставшихся вершин, а именно,

D[v3] = min (D[v3], D[v2]+c23, D[v4]+c43, D[v5]+c53, D[v6]+c63) = (5,7+, 5+, 2+1, 12+) = 3,

D[v4] = min (D[v4], D[v2]+c24, D[v3]+c34, D[v5]+c54, D[v6]+c64) = (5,7+, 3+, 2+2, 12+) = 4,

D[v5] = min (D[v5], D[v2]+ c25, D[v3]+ c35, D[v4]+ c45, D[v6]+ c65) = (2,7+, 3+, 4+, 12+) = 2,

D[v6] = min (D[v6], D[v2]+ c26, D[v3]+ c36, D[v4]+ c46, D[v5]+ c56) = (12,7+2, 3+, 4+, 2+) = 9.

Т.к. метки вершин изменились, то продолжаем процесс дальше. Результаты третьей и четвертой итераций совпали, значит итерационный процесс можно закончить, кроме того k = n-2 = 4.

Величины, стоящие в последнем столбце, и дают длины минимальных путей из вершины v1 до всех остальных вершин. Например, длина минимального пути из v1 в v2 равна 5, сам путь имеет вид: v1v5v3v2.

алгоритм форда беллман

Программа разбита на несколько модулей. Логика.cpp - главный файл проекта. В нем осуществляется запуск главного окна Form1().

Файл Form1.h отвечает за внешний вид главного окна, а именно: заголовок, пункты меню. Также в этом файле осуществляются сам алгоритм поиска минимальных путей между всеми парами вершин.

На рисунке 5 изображено стартовое окно программы:

Рисунок 5 - Стартовое окно программы.

Далее мы указываем количество вершин и рёбер в графе, после этого мы можем задать вес рёбер вручную или же заполнить их случайным образом, из цифр которые находятся в диапазоне случайных значений, которые мы можем выбрать на своё усмотрение. После заполнения матрицы нажимаем появившиеся кнопки «Вывести граф» и «Рассчитать пути» и получаем расстояние между всеми возможными парами вершин графа и его графическое изображение.

На рисунке 6. Показан результат работы программы.

Рисунок 6 - Результат работы программы.

Проведём различные тесты с программой использую различные символы для исходной матрицы инцидентности. В процессе тестирования программы проверялась реакция программы на введенные значения.

На рисунке 7 мы можем наблюдать реакцию программы на ввод некорректных символов.

Рисунок 7 - Обработка ошибки при вводе буквы.

На рисунке 8 изображена реакция программы на превышение максимального значения

Рисунок 8 - Результат при корректном вводе.

На рисунке 9 изображен результат работы программы при корректном вводе значений.

Рисунок 9 - Результат при корректном вводе.

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

При выполнении данной работы использовались функции Windows.form, описанные в заголовочном файле Windows.h для визуализации результатов работы.

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

В ходе тестирования были выявлены основные преимущества и недостатки изучаемого алгоритма.

1. Брайан Керниган, Деннис Ритчи - Язык программирования Си, 2-е издание, 2016.

2. Брюс Эккель - Философия C++. Введение в стандартный C++, 2-е издание, 2004.

3. Стивен Прата - Язык программирования C++. Лекции и упражнения, 6-е издание, 2017.

Приложение. Результаты работы программы на разных наборах исходных данных

Результаты работы программы показаны на Рисунках 10-12.

Рисунок 10 - Результат работы программы

Рисунок 11 - Результат работы программы

Рисунок 12 - Результат работы программы.

Размещено на Allbest.ru

Подобные документы

Понятие и сущность графы, методы решения задач по поиску кратчайших путей в ней. Особенности составления программного кода на языке программирования Pascal с использованием алгоритма Форда-Беллмана, а также порядок ее тестирования с ручным просчетом.

курсовая работа [1,2 M], добавлен 31.07.2010

Блок-схема алгоритма Флойда. Разработка его псевдокода в программе Microsoft Visual Studio. Программа реализации алгоритмов Беллмана-Форда. Анализ трудоемкости роста функции. Протокол тестирования правильности работы программы по алгоритму Флойда.

курсовая работа [653,5 K], добавлен 18.02.2013

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

презентация [449,3 K], добавлен 19.10.2014

Графы: определения, примеры, способы изображения. Смежные вершины и рёбра. Путь в ориентированном и взвешенном графе. Матрица смежности и иерархический список. Алгоритм Дейкстры - алгоритм поиска кратчайших путей в графе. Работа в программе "ProGraph".

презентация [383,8 K], добавлен 27.03.2011

Анализ алгоритмов нахождения кратчайших маршрутов в графе без отрицательных циклов: Дейкстры, Беллмана-Форда и Флойда-Уоршалла. Разработка интерфейса программы на языке C++. Доказательство "правильности" работы алгоритма с помощью математической индукции.

курсовая работа [1,5 M], добавлен 26.07.2013

Использование понятий из теории графов при разработке сетей и алгоритмов маршрутизации. Построение матрицы смежности и взвешенного ориентировочного графа. Результаты работы алгоритмов Дейкстры и Беллмана-Форда. Протоколы обмена маршрутной информацией.

курсовая работа [334,1 K], добавлен 20.01.2013

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

Алгоритм Беллмана – Форда - Bellman–Ford algorithm

Алгоритм Беллмана-Форда представляет собой алгоритм , который вычисляет кратчайший путь из одного источника вершины до всех остальных вершин в весовом орграфа . Он медленнее, чем алгоритм Дейкстры для той же проблемы, но более универсален, поскольку он способен обрабатывать графы, в которых некоторые веса ребер являются отрицательными числами. Алгоритм был впервые предложен Альфонсо Шимбелем ( 1955 ), но вместо этого назван в честь Ричарда Беллмана и Лестера Форда-младшего , опубликовавших его в 1958 и 1956 годах соответственно. Эдвард Ф. Мур также опубликовал вариант алгоритма в 1959 году , и по этой причине его также иногда называют алгоритмом Беллмана – Форда – Мура .

Отрицательные веса ребер встречаются в различных приложениях графов, отсюда и полезность этого алгоритма. Если граф содержит «отрицательный цикл» (т. Е. Цикл , сумма ребер которого равна отрицательному значению), достижимый из источника, тогда не существует самого дешевого пути: любой путь, имеющий точку на отрицательном цикле, можно сделать дешевле, если один более ходить вокруг отрицательного цикла. В таком случае алгоритм Беллмана – Форда может обнаружить отрицательный цикл и сообщить о нем.

СОДЕРЖАНИЕ

Алгоритм

Подобно алгоритму Дейкстры , Беллмана – Форда действует релаксация , в которой приближения к правильному расстоянию заменяются лучшими до тех пор, пока они в конечном итоге не достигнут решения. В обоих алгоритмах приблизительное расстояние до каждой вершины всегда является завышенным по сравнению с истинным расстоянием и заменяется минимумом своего старого значения и длиной вновь найденного пути. Однако алгоритм Дейкстры использует очередь приоритетов для жадного выбора ближайшей вершины, которая еще не была обработана, и выполняет этот процесс релаксации на всех ее исходящих ребрах; Напротив, алгоритм Беллмана – Форда просто расслабляет все ребра и делает это раз, где - количество вершин в графе. В каждом из этих повторений количество вершин с правильно рассчитанными расстояниями растет, из чего следует, что в конечном итоге все вершины будут иметь свои правильные расстояния. Этот метод позволяет применять алгоритм Беллмана – Форда к более широкому классу входных данных, чем алгоритм Дейкстры. | V | - 1 <\ displaystyle | V | -1>| V |

Беллман – Форд работает по времени , где и - количество вершин и ребер соответственно. О ( | V | ⋅ | E | ) <\ Displaystyle O (| V | \ cdot | E |)>| V | <\ displaystyle | V |>| E |

Проще говоря, алгоритм инициализирует расстояние до источника равным 0, а все остальные узлы - бесконечностью. Затем для всех краев, если расстояние до пункта назначения можно сократить, взяв край, расстояние обновляется до нового более низкого значения. На каждой итерации я , что края сканированные, алгоритм находит все кратчайшие пути по большей длине я ребра (и , возможно , некоторые пути длиннее , чем я края). Поскольку самый длинный путь без цикла может быть ребрами, ребра необходимо сканировать раз, чтобы гарантировать, что кратчайший путь был найден для всех узлов. Выполняется окончательное сканирование всех ребер, и если какое-либо расстояние обновляется, то был найден путь ребер длины , что может произойти только в том случае, если в графе существует хотя бы один отрицательный цикл. | V | - 1 <\ displaystyle | V | -1>| V | - 1 <\ displaystyle | V | -1>| V |

Доказательство правильности

Правильность алгоритма можно показать по индукции :

Лемма . После того, как я повторения для цикла,

если 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

Т.е. каждый цикл имеет неотрицательный вес.

Обнаружение отрицательных циклов

Когда алгоритм используется для поиска кратчайших путей, наличие отрицательных циклов является проблемой, не позволяющей алгоритму найти правильный ответ. Однако, поскольку он завершается при обнаружении отрицательного цикла, алгоритм Беллмана – Форда может использоваться для приложений, в которых необходимо искать эту цель - например, в методах отмены цикла в анализе сетевого потока .

Приложения в маршрутизации

Распределенный вариант алгоритма Беллмана – Форда используется в протоколах маршрутизации с вектором расстояния , например в протоколе маршрутной информации (RIP). Алгоритм распределен, потому что он включает несколько узлов (маршрутизаторов) в автономной системе (AS) , совокупность IP-сетей, обычно принадлежащих интернет-провайдеру. Он состоит из следующих этапов:

Каждый узел вычисляет расстояния между собой и всеми другими узлами в AS и сохраняет эту информацию в виде таблицы.

Каждый узел отправляет свою таблицу всем соседним узлам.

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

Основные недостатки алгоритма Беллмана – Форда в этой настройке следующие:

Он плохо масштабируется.

Изменения в топологии сети не отражаются быстро, поскольку обновления распространяются от узла к узлу.

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

Улучшения

Алгоритм Беллмана – Форда может быть улучшен на практике (хотя и не в худшем случае) путем наблюдения, что если итерация основного цикла алгоритма завершается без внесения каких-либо изменений, алгоритм может быть немедленно остановлен, поскольку последующие итерации будут больше не вносить изменений. С этим условием раннего завершения основной цикл может в некоторых случаях использовать намного меньше, чем | V | - 1 итерация, хотя худший вариант алгоритма остается без изменений. Все следующие улучшения сохраняют временную сложность наихудшего случая. О ( | V | ⋅ | E | )

Вариант алгоритма Беллмана-Форда, известный как алгоритм кратчайшего пути и быстрее , впервые описанный Муром (1959) , сокращает количество шагов релаксации, которые необходимо выполнить на каждой итерации алгоритма. Если вершина v имеет значение расстояния, которое не изменилось с момента последнего ослабления ребер из v , тогда нет необходимости ослаблять ребра из v во второй раз. Таким образом, по мере роста числа вершин с правильными значениями расстояния, количество исходящих ребер, которые необходимо ослаблять на каждой итерации, сокращается, что приводит к экономии времени с постоянным коэффициентом для плотных графов .

Йен (1970) описал еще одно усовершенствование алгоритма Беллмана – Форда. Его усовершенствование сначала назначает произвольный линейный порядок всем вершинам, а затем разбивает множество всех ребер на два подмножества. Первое подмножество E _f содержит все ребра ( v _i , v _j ) такие, что i < j ; вторая, E _b , содержит ребра ( v _i , v _j ) такие, что i > j . Каждая вершина посещается в порядке v ₁ , v ₂ , . v _{| V |} , расслабляя каждое выходящее из этой вершины ребро в E _f . Затем каждую вершину посещают в порядке v _{| V |} , v _{| V | −1} , . v ₁ , расслабляя каждое выходящее из этой вершины ребро в E _b . Каждая итерация основного цикла алгоритма после первой добавляет по крайней мере два ребра к набору ребер, релаксированные расстояния которых соответствуют правильным расстояниям кратчайшего пути: одно от E _f и одно от E _b . Эта модификация уменьшает наихудшее количество итераций основного цикла алгоритма с | V | - 1 к . | V | / 2 <\ displaystyle | V | / 2>

Другое усовершенствование, выполненное Баннистером и Эппштейном (2012) , заменяет произвольный линейный порядок вершин, использованный во втором улучшении Йена, случайной перестановкой . Это изменение делает наихудший случай улучшения Йена (в котором края кратчайшего пути строго чередуются между двумя подмножествами E _f и E _b ) очень маловероятным. При произвольном порядке перестановок вершин ожидаемое количество итераций, необходимых в основном цикле, не превышает максимума . | V | / 3 <\ displaystyle | V | / 3>

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

Содержание

История

Формулировка задачи

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

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

Решение задачи на графе без отрицательных циклов

Решим поставленную задачу на графе, в котором заведомо нет отрицательных циклов.

Путь, содержащий 0 рёбер, существует только до вершины s. Таким образом, A_i0 равно 0 при i = s, и в противном случае.

Теперь рассмотрим все пути из s в i, содержащие ровно j рёбер. Каждый такой путь есть путь из j − 1 ребра, к которому добавлено последнее ребро. Если про пути длины j − 1 все данные уже подсчитаны, то определить j-й столбец матрицы не составляет труда.

Так выглядит алгоритм поиска длин кратчайших путей в графе без отрицательных циклов:

Внешний цикл выполняется |V| - 1 раз, поскольку кратчайший путь не может содержать большее число ребер, иначе он будет содержать цикл, который точно можно выкинуть.

Вместо массива d можно хранить всю матрицу A, но это требует O(V²) памяти. Зато при этом можно вычислить и сами кратчайшие пути, а не только их длины. Для этого заведем матрицу P_ij.

Если элемент A_ij содержит длину кратчайшего пути из s в i, содержащего j рёбер, то P_ij содержит предыдущую вершину до i в одном из таких кратчайших путей (ведь их может быть несколько).

После выполнения этого алгоритма элементы A_i,j содержат длины кратчайших путей от s до i с количеством ребер j, и из всех таких путей следует выбрать самый короткий. А сам кратчайший путь до вершины i с j ребрами восстанавливается так:

Граф с отрицательными циклами

Каково худшее время работы алгоритма беллмана форда на графе с n вершинами

Алгоритмы поиска
кратчайшего пути

Нахождения наименьшего
остового дерева

Максимальные потоки
и паросочетания

Алгоритм Беллмана-Форда (Bellman-Ford algorithm)

Алгоритм Беллмана-Форда позволяет решить задачу о кратчайшем пути из одной вершины в общем случае, когда вес каждого из ребер может быть отрицательным. Для заданного взвешенного ориентированного графа G = (V, Е) с истоком s и весовой функцией w : Е —» R алгоритм Беллмана-Форда возвращает логическое значение, указывающее на то, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Если такой цикл существует, в алгоритме указывается, что решения не существует. Если же таких циклов нет, алгоритм выдает кратчайшие пути и их вес.

В этом алгоритме используется ослабление, в результате которого величина d[v], представляющая собой оценку веса кратчайшего пути из истока s к каждой из вершин v є V, уменьшается до тех пор, пока она не станет равна фактическому весу кратчайшего пути из s в v. Значение TRUE возвращается алгоритмом тогда и только тогда, когда граф не содержит циклов с отрицательным весом, достижимых из истока.

Формальное описание [вверх]

После инициализации в строке 1 всех значений d и prev, алгоритм осуществляет |V| — 1 проходов по ребрам графа. Каждый проход соответствует одной итерации цикла for в строках 2-4 и состоит из однократного ослабления каждого ребра графа. После |V| — 1 проходов в строках 5-8 проверяется наличие цикла с отрицательным весом и возвращается соответству- ющее булево значение.

Оценка сложности [вверх]

Алгоритм Беллмана-Форда завершает свою работу в течение времени O(V*E), поскольку инициализация в строке 1 занимает время O(V), на каждый из |V| — 1 проходов по ребрам в строках 2-4 требуется время в O(E), а на выполнение цикла for в строках 5-7 — время O(Е). .

Наглядное объяснение алгоритма Беллмана-Форда

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

Начнём с того, что все исходящие ребра записываются в таблице в алфавитном порядке.

Как и в алгоритме Дейкстры, создаётся таблица, в которой записывается расстояние до каждой вершины и предыдущая вершина. Расстояния для всех вершин, кроме исходной, инициализируются значением бесконечности. Расстояние обозначено переменной 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.

Во время третьей итерации алгоритм Беллмана-Форда снова перебирает все рёбра. Ребра AC и AE дают одинаковые результаты. Ребро BF теперь можно ослабить. Расстояние до B равно 9, поэтому расстояние до вершины F составит 9 + (-5) = 4. Вершина-предшественница F — это вершина В.

Рёбра CB и CH дают одинаковые результаты, поэтому таблица остаётся прежней. Ребро FG теперь можно ослабить. Расстояние до вершины F равно 4, поэтому расстояние до вершины G составит 4 + 2 = 6. Вершина, предыдущая по отношению к вершине G, — это вершина F.

Ребро GB теперь можно ослабить. Расстояние до вершины G равно 6, поэтому расстояние до B составит 6 + 4 = 10. Так как до вершины B можно добраться более коротким путём (через ребро CB), таблица остаётся прежней.

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

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

Строится таблица с расстояниями и вершинами-предшественницами. Расстояния инициализируются значением бесконечности для вершин A, B и C. Расстояние до S равно 0.

Видим, что первое ребро АВ ещё не может быть ослаблено, так же как и рёбра BC и СА. Зато может быть ослаблено ребро SA. Расстояние до S равно 0, поэтому расстояние до A составит 0 + 3 = 3. Вершина, предыдущая по отношению к вершине А, — это вершина S.

Ребро SB тоже можно ослабить. Расстояние до вершины B составит 0 + 6 = 6. Вершина-предшественница B — это вершина S.

Первая итерация завершена. Во время второй итерации снова перебираются все рёбра.

Ребро AB может быть ослаблено во время второй итерации. Расстояние до A равно 3, поэтому расстояние до вершины B составит 3 + 5 = 8. Так как расстояние до B уже меньше нового значения, значение B сохраняется. До ребра BC можно добраться, пройдя расстояние 6 + 2 = 8. Вершина, предыдущая по отношению к вершине С, — это вершина В.

Дальше перебирается ребро СА. Расстояние до C равно 8 единицам, поэтому расстояние до А (через ребро BC) составит 8 + (-10) = -2. Так как расстояние до А через ребро CA меньше, чем через ребро SA, расстояние до А обновляется.

Рёбра SA и SB не дают ничего лучшего, поэтому вторая итерация завершена. Начинается третья итерация.

Ребро АВ ослаблено. Расстояние до A в настоящее время равно -2, поэтому расстояние до B через ребро AB составит -2 + 5 = 3. Так как расстояние до B через AB меньше, чем через SB, расстояние становится теперь равным 3. Вершиной, предыдущей по отношению к вершине В, становится теперь вершина A.

Дальше ослабляется ребро BC. Текущее расстояние до B равно 3, поэтому расстояние до C составит 3 + 2 = 5. Расстояние до C становится теперь равным 5.

Ребро СА ослабляется. Расстояние до C составит 5 + (-10) = -5. Расстояние до вершины А обновляется на -5 единиц.

Рёбра SA и SB не дают результатов лучше. В это время все кратчайшие пути должны были быть найдены. В других итерациях никаких изменений быть не должно.

Ребро АВ ослаблено. Расстояние до A равно -5, поэтому расстояние до B составит -5 + 5 = 0. Расстояние до В становится теперь равным 0. Так как значение меняется на n-й итерации, значения будут меняться и на n+1-й итерации. Значения будут продолжать меняться неопределённое время. Если мы внимательно изучим граф, то увидим, что ABC даёт отрицательное значение: 5 + 2 + (-10) = -3.

Каково худшее время работы алгоритма беллмана форда на графе с n вершинами

Графы.Нахождение кратчайшего расстояния между двумя вершинами с помощью алгоритма Форда-Беллмана

Алгоритм Беллмана–Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| ? |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана–Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.

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

Решить задачу, т. е. найти все кратчайшие пути из вершины s до всех остальных, используя алгоритм Беллмана — Форда, это значит воспользоваться методом динамического программирования: разбить ее на типовые подзадачи, найти решение последним, покончив тем самым с основной задачей. Здесь решением каждой из таких подзадач является определение наилучшего пути от одного отдельно взятого ребра, до какого-либо другого. Для хранения результатов работы алгоритма заведем одномерный массив d[]. В каждом его i-ом элементе будет храниться значение кратчайшего пути из вершины s до вершины i (если таковое имеется). Изначально, присвоим элементам массива d[] значения равные условной бесконечности (например, число заведомо большее суммы всех весов), а в элемент d[s] запишем нуль. Так мы задействовали известную и необходимую информацию, а именно известно, что наилучший путь из вершины s в нее же саму равен 0, и необходимо предположить недоступность других вершин из s. По мере выполнения алгоритма, для некоторых из них, это условие окажется ложным, и вычисляться оптимальные стоимости путей до этих вершин из s(по материалам kvodo).

Каково худшее время работы алгоритма беллмана форда на графе с n вершинами
3204Susu228 → Просьба о помощи tuananhhlqt27 → Am i enough for CP shivamisation → Infinite loop problem in Linux Agnimandur → 1 on 1 Competitive Programming Coaching Luma → The faster way to submit on Codeforces a ntontrygubO_o → Giving negative feedback to contests in comments pani.natalia → CP in Syria. C137’s interview. Jon.Snow → CSES Tree section editorial m aroonrk → AtCoder Regular Contest 124 Announcement Triskpy → Whats the best strategy to practice efficiently. abdude824 → Bitsets, Bit Manipulations and Bitmasks Problems galactus → Need help in solving this problem AJAYHAYAGREEVE → Similar Problems Webservice kazama460 → (almost) Every Algorithms & Data Structures you needed to learn , with practice problems 150iq → How to solve this problem? Any ideas? bassdummy → Paradise Lost biranchi → Does long long int affect time complexity in comparison to the use of int? Master0fPuppets → Help on "Find power of power under mod of a prime awoo → Разбор Educational Codeforces Round 112 Ashishgup → India ICPC — Amritapuri 2020 Preliminary Round CodeRazer → The code runs fine on my machine but fails to give the right answer in codeforces
Блог пользователя Burunduk1
Автор Burunduk1, 10 лет назад ,
Друзья, будьте бдительны!

Для пояснения привожу код, который генерирует ацикличный граф без отрицательных ребер из 91 вершин и 121 ребра (а также перемешивает все ребра в случайном порядке), на котором код по ссылке выше делает более 1 000 000 добавлений в очередь.

Какие выводы отсюда я хочу сделать? Не добавляйте в начало очереди, вся проблема в этом! Люди, добавляющие в начало очереди, рискуют однажды доиграться и попасться на хорошие тесты.

Если же вы хотите, чтобы ваш Форд-Беллман работал быстро — пишите обычного Форд-Беллмана с очередью, т.е. добавляйте вершины всегда в конец очереди и следите за тем, чтобы каждая вершина хранилась в очереди не более чем в одном экземпляре. Почитать можно здесь: http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm

P.S. В правильном "Левите" (см., например, книжку И.В.Романовского, Дискретный Анализ) использовалось 2 очереди. Описанный там алгоритм и правда работает за O(VE). Но от "Форд-Беллмана с очередью" не отличается (улучшение не более чем в 2 раза).

UPD:

Только что услышал такой способ искать кратчайший путь в графе с отрицательными ребрами:

Берем Дейкстру с кучей и запускаем на графе с отрицательными ребрами (при этом всегда, когда расстояние до вершины улучшается, кладем ее в кучу) :-) Казалось бы, этот алгоритм просто просмотрит каждую вершину несколько раз. На самом деле, он тоже работает за экспоненциальное время. Идея теста: давайте превратим ребра веса W в цепочки из двух ребер — веса 2 k и ( W — 2 k ). Далее строим такой же тест, как показан выше.
ford bellman, левит, антитест, levit, fb Комментарии (33)
Сергей, если не секрет, что надоумило Вас анализировать этот алгоритм? Просто ради интереса, или кто-то напоролся на хороший тест?

Просто зашло обсуждение пока ехали в поезде, потому что об этой оптимизации было известно, что она хорошо улучшает в среднем, но непонятно почему работает вообще.

Паша правду говорит, в поезде СПБ-Петрозаводск оказалось, что я не умею доказывать оценку O(VE) для алгоритмов, добавляющих в начало. Оставлять это просто так было нельзя :-)

А что если не держать в очереди двух одинаковых вершин?

Если не класть в очередь вершину, которая уже в очереди, то эффект будет тот же.

Насколько реально построить двудольный граф в задаче о назначениях так, чтобы валился Левит (если мы решаем эту задачу через min-cost max-flow)?

Это очень просто. Возьмите таблицу умножения.

А как доказывается сложность левита при добавлении в конец?

Классический алгоритм Форд-Беллмана: будем V раз пытаться релаксировать все ребра.

Алгоритм Форд-Беллмана с очередью (также называемый "Левит с добавлением в конец"): будем на каждой из V итераций обрабатывать только ребра из тех вершин, расстояние которых улучшилось на предыдущей итерации (это как раз те вершины, что лежат в очереди).

Вроде бы очевидно, что второй алгоритм работает всегда не хуже, чем первый =)

Так было бы, если бы мы использовали две очереди (текущей итерации ФБ и новой), и добавляли с контролем дублирования во вторую. Здесь же мы в определенном случае релаксируем ребра "не вовремя", что может быть плохо (как в случае с добавлением в начало).

Ну у а как bfs работает Вы же понимаете? Там тоже в одной и той же очереди лежат вершины, до которых расстояние d, а потом вершины, до которых расстояние d+1.

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

Ну. )))) Ну и что?) Если класть вершины всегда, памяти O(E), но зато работает так же, как и bfs. А теперь заметим, что если не класть, то хуже не станет. Кажется, все. Я не прав?

Ага, всё правильно :)

Если не класть — хуже иногда станет. Действительно, пусть очередь вершин (2,1,3). Только что мы обновили расстояние до 1 и не положили ее в очередь. Теперь мы релаксируем вершину 2, она добавляет кучу вершин, очередь становится (1,3,[1],кучавершин). Теперь мы релаксируем 1, она обновляет расстояние до кучи вершин. Очередь становится (3,[1],кучавершин). Теперь релаксируем 3 и она обновляет расстояние до 1. Очередь становится ([1],кучавершин,1). Теперь мы должны кучу вершин релаксировать лишний раз.

Ну всё равно этот ФБ быстро работает. Рассмотрим весь процесс и разобьём его на шаги: каждый шаг — это полный проход по очереди с предыдущего шага. Тогда утвержнение: на i -ом шагу для всех вершин, до которых есть кратчайший путь из ≤ i рёбер, расстояние найдено правильно. Доказательство несложное — база индукции очевидна, переход — если есть кратчайший путь из i рёбер вида . - u - v , то на i - 1 'ом шаге расстояние до u точно было правильным, а значит, до окончания i -ого шага u с правильным расстоянием хоть раз была извлечена из очереди (и из неё были проведены все возможные релаксации). А значит, расстояние до v посчитано правильно.

Подумал над этим внимательно, и понял весьма простое сведение одной очереди к двум независимым. Представим, что перед началом новой итерации мы релаксируем все вершины, которых нет в очереди этой итерации потому, что они в прошлой были последний раз обновлены до выхода. Будет, будто мы новую и старую итерации храним независимо. Но релаксация этих вершин ни к чему не приведет.

Вроде, разобрался, спасибо!
← Rev. 2 → +47
Пользуясь случаем, напишу про самый быстрый из известных мне вариантов Форда-Беллмана (насколько я помню, автор этого варианта — Tarjan).

Пусть мы хотим использовать алгоритм Форда-Беллмана не только для поиска кратчайших путей, но и для проверки того, есть ли в графе отрицательный цикл. Довольно естественная идея — искать циклы в метках from (которые обычно поддерживаются для восстановления кратчайших путей). В "нормальном" состоянии эти метки образуют лес, и если в этом лесе внезапно появился цикл — то это и будет отрицательный цикл в графе. Так что поддерживая лес меток from, можно быстро проверять, есть ли в графе отрицательные циклы.

Так вот, оказывается, если поддерживать этот лес в процессе алгоритма, можно его сильно ускорить следующим образом. Предположим, мы сделали релаксацию />. У вершины v есть поддерево в нашем лесе, некоторые вершины <w_i> которого могут лежать в очереди. Заметим, что поскольку мы только что прорелаксировали расстояние до v , все оценки расстояний до <w_i> на данный момент неправильные, поэтому из них бесполезно делать релаксации, пока мы не обновим расстояния до них. Это наблюдение и даёт оптимизацию: после релаксации />выкинем все вершины поддерева v из очереди и удалим из леса все рёбра поддерева.

В итоге получается следующий рецепт: будем выполнять обычный алгоритм Форда-Беллмана с очередью, поддерживая лес меток from. При релаксации в какую-то вершину убиваем её поддерево в лесе, удаляя вершины этого поддерева из очереди.

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

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


Как снять потолок на инфинити fx35

Bmw f700gs замена масла

Change oil soon рено меган 2 как сбросить

Хендай солярис рейтинг безопасности

Коды неисправности лада веста