Самостоятельная работа на тему: > Студент группы №233-21 Ат-Сервис Факультета "Компьютерный инжиниринг " Ражабов Хаётжон Проверил

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

Случай отрицательного цикла.

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


void solve() {
vector<int> d (n, INF);
d[v] = 0;
vector<int> p (n, -1);
int x;
for (int i=0; i<n; ++i) {
x = -1;
for (int j=0; j<m; ++j)
if (d[e[j].a] < INF)
if (d[e[j].b] > d[e[j].a] + e[j].cost) {
d[e[j].b] = max (-INF, d[e[j].a] + e[j].cost);
p[e[j].b] = e[j].a;
x = e[j].b;
}
}
 
if (x == -1)
cout << "No negative cycle from " << v;
else {
int y = x;
for (int i=0; i<n; ++i)
y = p[y];
 
vector<int> path;
for (int cur=y; ; cur=p[cur]) {
path.push_back (cur);
if (cur == y && path.size() > 1) break;
}
reverse (path.begin(), path.end());
 
cout << "Negative cycle: ";
for (size_t i=0; i<path.size(); ++i)
cout << path[i] << ' ';
}}


Поскольку при наличии отрицательного цикла за  итераций алгоритма расстояния могли уйти далеко в минус (по всей видимости, до отрицательных чисел порядка  ), в коде приняты дополнительные меры против такого целочисленного переполнения:


d[e[j].b] = max (-INF, d[e[j].a] + e[j].cost);


В приведённой выше реализации ищется отрицательный цикл, достижимый из некоторой стартовой вершины  ; однако алгоритм можно модифицировать, чтобы он искал просто любой отрицательный цикл в графе. Для этого надо положить все расстояния  равными нулю, а не бесконечности — так, как будто бы мы ищем кратчайший путь изо всех вершин одновременно; на корректность обнаружения отрицательного цикла это не повлияет.
Задача:


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

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

Алгоритм:Ниже приведены подробно расписанные шаги.
Входные данные: Граф и начальная вершина src.
Выходные данные: Кратчайшее расстояние до всех вершин от src. Если попадается цикл отрицательного веса, то самые короткие расстояния не вычисляются, выводится сообщение о наличии такого цикла.

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

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

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

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

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

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

Реализация:

# Python program for Bellman-Ford's single source
# shortest path algorithm.