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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Алгоритм Беллмана—Форда - алгоритм пошуку найкоротшого шляху в зваженому графі. Знаходить найкоротші шляхи від однієї вершини графа до всіх інших. На відміну від алгоритму Дейкстри, алгоритм Беллмана—Форда допускає ребра з негативною вагою. Запропоновано незалежно Річардом Беллманом і Лестером Фордом.



Історія[ред.ред. код]

Алгоритм носить ім'я двох американських вчених: Річарда Беллмана (Richard Bellman) і Лестера Форда (Lester Ford). Форд фактично винайшов цей алгоритм в 1956 році при вивченні іншої математичної задачі, підзадача якої звелася до пошуку найкоротшого шляху в графі, і Форд зробив начерк остаточного вирішення завдання цього алгоритма. Беллман в 1958 р. опублікував статтю, присвячену конкретно завданню знаходження найкоротшого шляху, і в цій статті він чітко сформулював алгоритм у тому вигляді, в якому він відомий нам зараз.

Алгоритм маршрутизації RIP (алгоритм Беллмана - Форда) був вперше розроблений в 1969 році, як основний для мережі ARPANET.

Формулювання задачі[ред.ред. код]

Дано орієнтований або неорієнтований граф  G(V, E) зі зваженими ребрами. Довжиною шляху ( d[ ] ) назвемо суму ваг ребер, що входять в цей шлях. Вхідними даними для алгоритму є числа, список ребер, та номер стартовою вершини. Потрібно знайти найкоротші шляхи від початкової вершини до всіх вершин графа. Алгоритм Беллмана-Форда повертає логічне значення, яке вказує на те, чи міститься в графі цикл з негативною вагою, досяжний з витоку. Якщо такий цикл існує у графі  G , алгоритм повідомляє, що найкоротших шляхів не існує. Якщо ж таких циклів немає, алгоритм видає найкоротші шляхи і їх вагу.

Сам алгоритм Форда-Беллмана представляє з себе кілька фаз. На кожній фазі проглядаються всі ребра графа, і алгоритм намагається справити релаксацію (relax, ослаблення) уздовж кожного ребра  (a,b) ваги  c. Релаксація вздовж ребра - це спроба поліпшити значення  d [b] значенням  d[a]+c . Фактично це означає, що ми намагаємося поліпшити значення для вершини  b , корстуючсь ребром  (a,b) і поточним значенням для вершини  a . Стверджується, що достатньо  n-1 фази алгоритму, щоб коректно порахувати довжини всіх найкоротших шляхів у графі (цикли негативного ваги відсутні). Для недосяжних вершин відстань  d[ ] залишиться рівним нескінченності.

Псевдокод[ред.ред. код]

 for (k = 0 \; .. \; n-2)
    for (v \in V)
       for (u : vu \; \in E)
          d[k+1][u] \gets \min(d[k + 1][u], \; d[k][v] + \omega(uv))

Оцінка складності[ред.ред. код]

Якщо граф заданий списком ребер: ініціалізація потребує  O(V) часу, кожен з  |V| - 1 проходів потребує  O(E) часу, прохід по усім ребрам для перевірки наявності негативного циклу займає  O(E) часу. Отже алгоритм працює за  O(VE) часу.

Якщо граф заданий матрицею суміжності, то алгоритм буде виконуватись за  O(E^3) часу.

Вирішення задачі на графі без негативних циклів[ред.ред. код]

Для алгоритму Форда- Беллмана-, на відміну від багатьох інших графових алгоритмів, більш зручно представляти граф у вигляді одного списку всіх ребер (а не списків ребер - ребер з кожної вершини). У реалізації заводиться структура даних  edge для ребра. Вхідні дані для алгоритма є числа  n,m , список  e ребер, та номер стартовой початкової вершини  v . Всі номера вершин нумеруються з  0 по  n-1 .

Найпростіша реалізація[ред.ред. код]

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);
	}

Константу  INF треба підібрати таким чином, щоб вона перевершувала всі можливі довжини шляхів. Перевірка if (d[e[j].a] < INF) потрібна, тільки якщо граф містить ребра негативної ваги: без такої перевірки б відбувалися релаксації з вершин, до яких шляху ще не знайшли, і з'являлися б некоректні відстані.

Покращена реалізація та отримання найкоротших шляхів[ред.ред. код]

Цей алгоритм можна дещо прискорити: часто відповідь знаходиться вже за кілька фаз, а що залишилися фази ніякої корисної роботи не відбувається, лише даремно проглядаються всі ребра. Тому встановимо прапорець того, змінилося щось на поточній фазі чи ні, і якщо на якійсь фазі нічого не сталося, то алгоритм запиняється. (Ця оптимізація не покращує асимптотику, тобто на деяких графах і раніше будуть потрібні всі  n-1 фаза, але значно прискорює поведінка алгоритму "в середньому", тобто на випадкових графах).

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_t i=0; i<path.size(); ++i)
			cout << path[i] << ' ';
	}
}

Для виводу найкоротших шляхів ми спочатку проходимо по нащадкам, починаючи з заданої вершини  t і зберігаємо весь пройдений шлях в списку  path . У цьому списку виходить найкоротший шлях від  v до  t , але в зворотному порядку, тому ми викликаємо reverse від нього і потім виводимо.

Приклад[ред.ред. код]

На малюнку у вершинах графа показані значення атрибутів  d на кожному етапі роботи алгоритму, а виділені ребра вказують на значення попередників: якщо ребро  (u, v) виділено, то  prev [v] = u . У розглянутому прикладі при кожному проході ребра послаблюються в наступному порядку:(t, х), (t, у), (t, z), (x, t), (у, х), (у, z), (z , x), (z, s), (s, t), (s, y). У частині а малюнка показана ситуація, що склалася безпосередньо перед першим проходом по ребрах. У частинах б-д проілюстрована ситуація після кожного чергового проходу по ребрах. Значення атрибутів  d і  prev , наведені в частині д, є остаточними.

Вирішення задачі на графі з негативним циклом[ред.ред. код]

При наявності негативного циклу виникають складнощі, пов'язані з тим, що відстані до всіх вершин на цьому циклі, а також відстані до досяжних з цього циклу вершин не визначені - вони повинні бути рівні мінус нескінченності. Отже, якщо не обмежувати число фаз числом n-1, то алгоритм Форда- Беллмана буде робити релаксації серед всіх вершин цього циклу і вершин, досяжних з нього і буде працювати нескінченно, постійно покращуючи відстані до цих вершин . Звідси ми отримуємо критерій наявності досяжного циклу негативної ваги : якщо після n-1 фази ми виконаємо ще одну фазу, і на ній відбудеться хоча б одна релаксація , то граф містить цикл негативного ваги, досяжний з v; в іншому випадку, такого циклу немає. Більше того, якщо такий цикл виявився, то алгоритм Форда-Беллмана можна модифікувати таким чином, щоб він виводив сам цей цикл у вигляді послідовності вершин, що входять до нього. Для цього досить запам'ятати номер вершини x, в якій сталася релаксація на n - ої фазі. Ця вершина буде або лежати на циклі негативного ваги, або вона досяжна з нього. Щоб отримати вершину, яка гарантовано лежить на циклі, достатньо, наприклад, n раз пройти по предкам, починаючи від вершини x. Отримавши номер y вершини, що лежить на циклі, треба пройтися від цієї вершини по предкам, поки ми не повернемося в цю ж вершину y (а це обов'язково станеться , бо релаксації в циклі негативного ваги відбуваються по колу).

Реалізація[ред.ред. код]

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] << ' ';
	}
}

Приклад[ред.ред. код]

Отримуємо негативний цикл з вершин 1-4-2.

Після закінчення основних ітерацій алгоритму проходить перевірка на наявність негативних циклів. Для даного графа під час перевірки буде знайдено ребро, яке можна послабити, що є показником існування циклу з дуг негативних ваг. Цикл виявлений, алгоритм припиняє роботу.

Література[ред.ред. код]

  • R. Bellman: On a Routing Problem // Quarterly of Applied Mathematics. 1958. Vol 16, No. 1. C. 87-90, 1958.
  • L. R. Ford, Jr., D. R. Fulkerson. Flows in Networks, Princeton University Press, 1962.

Дивіться також[ред.ред. код]

Дослідження операцій

Посилання[ред.ред. код]

Реалізація алгоритму Белмана - Форда на e-maxx.ru
Реалізіція алгоритму пошуку негативного циклу на e-maxx.ru