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

Добавил пользователь Владимир З.
Обновлено: 19.09.2024

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

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] .

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

Постановка задачи

В задаче рассматривается взвешенный граф — то есть граф, каждому ребру которого сопоставлено некоторое число, называемое его весом. Вес ребра, ведущего из вершины u в вершину v, мы будем обозначать weight[u, v].
Требуется найти путь из вершины u в вершину v, сумма весов ребер которого минимальна. Эту сумму весов будем называть расстоянием от вершины u до вершины v и обозначать dist[u, v].

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

Давайте придумаем что-нибудь простое

Рассмотрим какое-нибудь ребро (v, w). Что мы можем сказать про расстояния до его концов? Очевидно, dist[u, w] ≤ dist[u, v] + weight[v, w].

Пусть dist[u, v] = K. Это значит, что существует путь от u до v весом K. Добавим к этому пути ребро (v, w). Получим путь от u до w весом K + weight[v, w]. Так как расстояние от u до w — минимальная из длин всех путей, соединяющих u и v, dist[u, w] ≤ K + weight[v, w]

Давайте будем действовать итерационно. Изначально известно расстояние только до начальной вершины — оно равно 0. В каждый момент времени мы можем проверить выполнение свойства для какого-нибудь ребра и, если оно нарушено, улучшить существующую оценку расстояния до конечной вершины ребра. Это процедура называется релаксацией.

Слова ничто, покажите мне код!

В коде предполагается, что граф хранится в vector>> edges, где edges[v] — вектор всех ребер, исходящих из вершины v. В ребре edges[v][i] первое поле — конечная вершина ребра, второе — его вес. INF — это некоторая константа, заведомо большая, чем любое получающееся расстояние. Обозначает отсутствие известного пути.

Как много ресурсов надо алгоритму?

Помимо графа и значений, выдающихся в ответ, мы храним лишь константное количество памяти, следовательно, количество памяти, требующееся алгоритму — O(1) + <память на хранение графа и ответа>= O(V + E) = O(E).
Релаксация каждого ребра занимает константное количество действий. Всего ребер — E, релаксация всех ребер производится V раз. Таким образом, временная сложность алгоритма — O(VE).

А если я педант?

База: k = 0 очевидно, путь из начальной вершины в нее же найден верно
Предположение: после k итераций для всех вершин v, до которых существует кратчайший путь, состоящий из не более, чем k ребер, dist[v] равно расстоянию от начальной вершины до v
Шаг: рассмотрим некоторую вершину w, до которой существует кратчайший путь, состоящий из k + 1 ребра.
- Обозначим предпоследнюю вершину в пути от u до w, как v.
- Для v существует кратчайший путь из k вершин (например, начало кратчайшего пути до w).
- Значит, кратчайший путь до v был найден на предыдущей итерации. Проведя релаксацию ребра (v, w) на k + 1-ой итерации, мы получим верное значение расстояния до вершины w.
- Заметим, что при релаксации какого-либо другого ребра мы не могли получить значения, меньшего, чем верное расстояние, поскольку каждой релаксации ребра (x, w) можно поставить в соответствие путь из начальной вершины в w соответствующей длины.
А как же путешествия во времени?

В доказательстве не зря была сделана оговорка — ищутся все существующие кратчайшие пути. Существует ситуация, в которой есть путь от u до v, но нет кратчайшего пути от u до v — например, если обе эти вершины входят в цикл отрицательного веса. Это является математическим эквивалентом случая, когда переходы между вершинами — это порталы, причем такие, которые могут забросить как в прошлое, так и в будущее. Присутствие цикла отрицательного веса означает, что пройдя по нему нужное количество оборотов, можно оказаться в прошлом так далеко, как хочется.
Алгоритм Форда-Беллмана предоставляет и способ нахождения таких циклов: если циклов нет — значит, все кратчайшие пути не длиннее, чем из V — 1 ребра, и на последней итерации не будет произведено ни одной релаксации. Все ребра, релаксация которых производилась на последней итерации, лежат в циклах отрицательного веса, достижимых из начальной верщины.

Количество путей длины [math]k[/math] рёбер можно найти с помощью метода динамического программирования.
Пусть [math]d[k][u][/math] — количество путей длины [math]k[/math] рёбер, заканчивающихся в вершине [math]u[/math] . Тогда [math] d[k][u] = \sum\limits_ d[k-1][v] [/math] .

Аналогично посчитаем пути кратчайшей длины. Пусть [math]s[/math] — стартовая вершина. Тогда [math] d[k][u] = \min\limits_(d[k-1][v] \: + \: \omega(u, v))[/math] , при этом [math]d[0][s] = 0[/math] , а [math]d[0][u] = +\infty [/math]

Если существует кратчайший путь от [math]s[/math] до [math]t[/math] , то [math] \rho(s, \, t) \: = \: \min\limits_ d[k][t][/math]

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

Также релаксацию можно свести к одномерному случаю, если не хранить длину пути в рёбрах. Одномерный массив будем обозначать [math]d'[/math] , тогда [math]d'[u] = \min(d'[u], \; d'[v] + \omega(vu))[/math]

Пусть [math]G = (V, E)[/math] — взвешенный ориентированный граф, [math] s [/math] — стартовая вершина. Тогда после завершения [math]k[/math] итераций цикла [math]\mathrm[/math] выполняется неравенство [math] \rho(s, u) \leqslant d'[u] \leqslant \min\limits_ d[i][u][/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_ d[i][u][/math] для всех [math]u[/math] . Тогда после [math]k[/math] итераций [math] \rho(s, v) = \min\limits_ (\rho(s, u) + \omega(uv)) \leqslant \min\limits_ (d'[u] + \omega(uv)) = d'[v][/math] .
1. [math]\min\limits_ d[i][u] = d[k+1][u][/math]
2. [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]G = (V, E) [/math] — взвешенный ориентированный граф, [math] s [/math] — стартовая вершина. Тогда после завершения [math] |V| - 1 [/math] итераций цикла для всех вершин, достижимых из [math]s[/math] , выполняется равенство [math] d[v] = \delta (s, v) [/math] .

Рассмотрим произвольную вершину [math]v[/math] , достижимую из [math]s[/math] . Пусть [math]p = \langle v_0. v_ \rangle [/math] , где [math]v_0 = s[/math] , [math]v_ = v[/math] — кратчайший ациклический путь из [math] s [/math] в [math] v [/math] . Путь [math] p [/math] содержит не более [math] |V| - 1 [/math] ребер. Поэтому [math]k \leqslant |V| - 1[/math] .

Докажем следующее утверждение:

После [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 = (V, E) [/math] — взвешенный ориентированный граф, [math] s [/math] — стартовая вершина. Если граф [math] G [/math] не содержит отрицательных циклов, достижимых из вершины [math] s [/math] , то алгоритм возвращает [math] true [/math] и для всех [math] v \in V \ d[v] = \delta (s, v)[/math] . Если граф [math] G [/math] содержит отрицательные циклы, достижимые из вершины [math] s [/math] , то алгоритм возвращает [math] false [/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 [/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] , где [math] v_0 = v_ [/math] , достижимый из вершины [math] s [/math] . Тогда [math]\sum\limits_^ <\omega (v_, v_)> \lt 0 [/math] .

Предположим, что алгоритм возвращает [math] true [/math] , тогда для [math] i = 1. k [/math] выполняется [math] d[v_] \leqslant d[v_] + \omega (v_, v_) [/math] .

Просуммируем эти неравенства по всему циклу: [math]\sum\limits_^ \leqslant \sum\limits_^ ]> + \sum\limits_^ <\omega (v_, v_)> [/math] .

Из того, что [math] v_0 = v_ [/math] следует, что [math] \sum\limits^_ ]> = \sum \limits_^ ]> [/math] .

Инициализация занимает [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] . Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.

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

Что такое арбитраж

Арбитраж — это несколько логически связанных сделок, направленных на извлечение прибыли из разницы в ценах на одинаковые или связанные активы в одно и то же время на разных рынках (пространственный арбитраж), либо на одном и том же рынке в разные моменты времени (временной арбитраж).

В качестве простого примера рассмотрим пространственный арбитраж. В Нью-Йорке и Лондоне можно заключить сделки по покупке долларов за евро и евро за доллары. В Нью-Йорке это можно делать по курсу 4 доллара за 3 евро, а в Лондоне — по курсу 5 долларов за 3 евро. Такая разница курсов открывает возможность для пространственного арбитража.

Имея 4 доллара, в Нью-Йорке на них можно купить 3 евро. После этого в Лондоне купить за эти 3 евро 5 долларов. Как можно заметить, такая несложная последовательность сделок приносит 1 доллар прибыли на каждые вложенные 4 доллара. Соответственно, если изначально имеется 4 миллиона долларов, то и прибыль будет уже в миллион.

Когда обменные курсы (спред не рассматриваем) для одной и той же валютной пары отличаются, то последовательность сделок, необходимых для реализации арбитражной стратегии, очень простая. В случае, если курс для одной валютной пары фиксирован, но торгуются несколько валютных пар параллельно, арбитраж также возможен, но последовательность сделок уже будет нетривиальной. К примеру, можно купить 4 евро за 5 долларов, 3 фунта за 4 евро, а потом 6 долларов за 3 фунта. Прибыль от такой последовательности сделок составит 1 доллар на каждые 5 вложенных долларов.

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

Переход к алгоритмической задаче

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

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

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

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

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

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

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

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

Тем, кому привычнее разбираться с кодом, должна помочь следующая небольшая реализация описанного выше алгоритма на Kotlin'е.

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

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

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

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

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

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

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

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

Ребро, релаксация которого обновляет расстояние до вершины, найдено. Это подтверждает наличие цикла отрицательной длины. Теперь необходимо найти сам этот цикл. Важно, что вершина, расстояние до которой сейчас обновилось, может быть как внутри цикла, так и вне него. В примере это вершина и она вне цикла. Далее необходимо обратиться к ссылкам на предыдущие вершины, которые аккуратно обновлялись на всех шагах алгоритма. Чтобы гарантированно попасть в цикл, необходимо отступить назад на вершин, пользуясь этими ссылками.

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

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

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

Заключение

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

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