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

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

Пусть дан ориентированный взвешенный граф G с n вершинами и m рёбрами, и указана некоторая стартовая вершина v. Требуется найти длины кратчайших путей от вершины v до всех остальных вершин.

Также как и Дейкстра алгоритм Форда-Беллмана ищет расстояние от 1 вершины до всех остальных, но работает с отрицательными ребрами.

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

d - это массив кратчайших длин от стартовой вершины, также как и в Дейкстре, изначально заполняем максмально большими числами, кроме стартовой вершины в которой надо поставить 0.
Для хранения ребер используется не матрица смежности или весовая матрица, а список, в котором указывается из какого узла выходит ребро(from), в какое оно приходит(to) и его вес (cost):

struct edge {
	int from, to, cost;
};
 
vector<edge> edges;

Константа INF обозначает число "бесконечность" — её надо подобрать таким образом, чтобы она заведомо превосходила все возможные длины путей.

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

d[v] = 0;
	for (int i=0; i<n-1; ++i)
		for (int j=0; j<m; ++j)
			if (d[edges[j].from] < INF)
				d[edges[j].to] = min (d[edges[j].to], d[edges[j].from] + edges[j].cost);

или немного покороче с использованием синтаксиса С++ 11:

d[v] = 0;
	for (int i=0; i<n-1; ++i)
		for (edge j: edges)
			if (d[j.from] < INF)
				d[j.to] = min (d[j.to], d[j.from] + j.cost);

Рассмотрим пример работы алгоритма:

Возьмем простой ориентированный граф с 5-ую узлами, 4-мя ребрам и с весом ребер равным 1.

Введем список ребер именно в таком порядке:
4 5 1
3 4 1
2 3 1
1 2 1

Исходные значения в массиве кратчайших длин:

inf

где inf - это должно быть такое подобранное целое число, которое бы всегда было больше веса ребра.

после 1-го прохода:

inf

после 2-го прохода:

inf

после 3-го прохода:

inf

после 4-го прохода:

Если бы мы подавали ребра в порядке от 1 до последнего, то нахождение кратчайших длин может быть и после 1-го прохода.

Task

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.

Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.

Входные данные

Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).

Выходные данные

Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.

Ввод	Вывод
6 4 1 2 10 2 3 10 1 3 100 4 5 -10	0 10 20 30000 30000 30000

C++

Write a program below
#include <iostream> #include <vector> using namespace std; const int INF = 1e9; struct edge { int from, to, w; }; vector <edge> edges; int d[201]; int main() { int n, m, from, to, w; cin >> n >> m; for (int i = 1; i <= n; i++) { d[i] = INF; } for (int i = 0; i < m; i++) { edge e; cin >> e.from >> e.to >> e.w; edges.push_back(e); } d[1] = 0; for (int i = 1; i < n; i++) {

} for (int i = 1; i <= n; i++) { if (d[i] == INF) cout << 30000 <<" " ; else cout << d[i] << " "; } return 0; }

Write a program below

#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9;

struct edge
{
    int from, to, w;
};

vector <edge> edges;
int d[201];

int main()
{
    int n, m, from, to, w;

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }

    for (int i = 0; i < m; i++)
    {
      edge e;
        cin >> e.from >> e.to >> e.w;
        edges.push_back(e);
    }

    d[1] = 0;

    for (int i = 1; i < n; i++)
    {

 }

    for (int i = 1; i <= n; i++)
    {
        if (d[i] == INF)
            cout << 30000 <<" " ;
        else
            cout << d[i] << " ";
    }

    return 0;
}

Your last submission is saved in the editor window.

Results:

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

All results:

Education

My Account

About us

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

№ 1/6 Форд-Беллман: Начало

All results:

Education

My Account

About us