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

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

Решить задачу, т. е. найти все кратчайшие пути из вершины s до всех остальных, используя алгоритм Беллмана — Форда, это значит воспользоваться методом динамического программирования: разбить ее на типовые подзадачи, найти решение последним, покончив тем самым с основной задачей. Здесь решением каждой из таких подзадач является определение наилучшего пути от одного отдельно взятого ребра, до какого-либо другого. Для хранения результатов работы алгоритма заведем одномерный массив d[]. В каждом его i-ом элементе будет храниться значение кратчайшего пути из вершины s до вершины i (если таковое имеется). Изначально, присвоим элементам массива d[] значения равные условной бесконечности (например, число заведомо большее суммы всех весов), а в элемент d[s] запишем нуль. Так мы задействовали известную и необходимую информацию, а именно известно, что наилучший путь из вершины s в нее же саму равен 0, и необходимо предположить недоступность других вершин из s. По мере выполнения алгоритма, для некоторых из них, это условие окажется ложным, и вычисляться оптимальные стоимости путей до этих вершин из s.

Задан граф G=(V, E), n=|V|, а m=|E|. Обозначим смежные вершины этого графа символами v и u (vÎV и uÎV), а вес ребра (v, u) символом w. Иначе говоря, вес ребра, выходящего из вершины v и входящего в вершину u, будет равен w. Тогда ключевая часть алгоритма Беллмана — Форда примет следующий вид:

Для i от 1 до n-1 выполнять
Для j от 1 до m выполнять
Если d[v] + w(v, u) < d[u] то
d[u] < d[v] + w(v, u)

На каждом n-ом шаге осуществляются попытки улучшить значения элементов массива d[]: если сумма, составленная из веса ребра w(v, u) и веса хранящегося в элементе d[v], меньше веса d[u], то она присваивается последнему.

void bellman_ford(int n, int s)
{
int i, j;

for (i=0; i<n; i++) d[i]=inf;
d[s]=0;

for (i=0; i<n-1; i++)
for (j=0; j<e; j++)
if (d[edge[j].v]+edge[j].w<d[edge[j].u])
d[edge[j].u]=d[edge[j].v]+edge[j].w;

for (i=0; i<n; i++) if (d[i]==inf)
cout<<endl<<start<<"->"<<i+1<<"="<<"Not";
else cout<<endl<<start<<"->"<<i+1<<"="<<d[i];
}

Дата добавления: 2015-07-26; просмотров: 140; Нарушение авторских прав

Мы поможем в написании ваших работ!