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

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

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

 

 

 

 

 

                                                       Коды.

Простейшая реализация:

struct edge {

int a, b, cost;

};

int n, m, v;

vector<edge> e;

const int INF = 1000000000;

 

void solve() {

vector<int> d (n, INF);

d[v] = 0;

for (int i=0; i<n-1; ++i)

for (int j=0; j<m; ++j)

if (d[e[j].a] < INF)

d[e[j].b] = min (d[e[j].b], d[e[j].a] + e[j].cost);

// вывод d, например, на  экран

}

 

Улучшенная реализация:

void solve() {

vector<int> d (n, INF);

d[v] = 0;

for (;;) {

bool any = false;

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] = d[e[j].a] + e[j].cost;

any = true;

}

if (!any)  break;

}

// вывод d, например, на  экран

}

 

Восстановление  путей.

Реализация Беллмана-Форда с восстановлением пути до какой-то заданной вершины :

void solve() {

vector<int> d (n, INF);

d[v] = 0;

vector<int> p (n, -1);

for (;;) {

bool any = false;

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] = d[e[j].a] + e[j].cost;

p[e[j].b] = e[j].a;

any = true;

}

if (!any)  break;

}

 

if (d[t] == INF)

cout<< "No path from " << v << " to " << t << ".";

else {

vector<int>path;

for (int cur=t; cur!=-1; cur=p[cur])

path.push_back (cur);

reverse (path.begin(), path.end());

 

cout<< "Path from " << v << " to " << t << ": ";

for (size_ti=0; i<path.size(); ++i)

cout<< path[i] << ' ';

}

}

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

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

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_ti=0; i<path.size(); ++i)

cout<< path[i] << ' ';

}

}

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

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

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

 

 

 

 

 

 

 

 

 

 

                               

                                Список использованных источников:

1. Липский В. Комбинаторика для программистов.–М.: «Мир», 1998. - 200 с.
2. Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы: построение и анализ. – М.: МЦНМО, 1990.
3. Алгоритм Беллмана-Форда –URL: http://e-maxx.ru/algo/ford_bellman (дата обращения 02.06.12)