«

»

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

История алгоритма связана сразу с тремя независимыми математиками: Лестером Фордом, Ричардом Беллманом и Эдвардом Муром. Форд и Беллман опубликовали алгоритм в 1956 и 1958 годах соответственно, а Мур сделал это в 1957 году. И иногда его называют алгоритмом Беллмана – Форда – Мура. Метод используется в некоторых протоколах дистанционно-векторной маршрутизации, например в RIP (Routing Information Protocol – Протокол маршрутной информации).

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

Решить задачу, т. е. найти все кратчайшие пути из вершины 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], то она присваивается последнему.

Код программы на C++:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include "stdafx.h"
#include <iostream>
#define inf 100000
using namespace std;
struct Edges{
int u, v, w;
};
const int Vmax=1000;
const int Emax=Vmax*(Vmax-1)/2;
int i, j, n, e, start;
Edges edge[Emax];
int d[Vmax];
//алгоритм Беллмана-Форда
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];
}
//главная функция
void main()
{
setlocale(LC_ALL, "Rus");
int w;

cout<<"Количество вершин > "; cin>>n;
e=0;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
cout<<"Вес "<<i+1<<"->"<<j+1<<" > "; cin>>w;
if (w!=0)
{
edge[e].v=i;
edge[e].u=j;
edge[e].w=w;
e++;
}
}

cout<<"Стартовая вершина > "; cin>>start;
cout<<"Список кратчайших путей:";
bellman_ford(n, start-1);
system("pause>>void");
}

 

Код программы на Pascal:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
program Ford_Bellman;
uses crt;
const
inf=100000;
Vmax=1000;
Emax=Vmax*(Vmax-1) div 2;
type Edges=record
u, v, w: integer;
end;
Var
i, j, e, n, w, start: integer;
edge: array[1..Emax] of Edges;
d: array[1..Vmax] of integer;
{алгоритм Беллмана-Форда}
procedure FB(n, s: integer);
begin
for i:=1 to n do d[i]:=inf;
d[s]:=0;

for i:=1 to n-1 do
for j:=1 to e-1 do
if d[edge[j].v]+edge[j].w<d[edge[j].u] then
d[edge[j].u]:=d[edge[j].v]+edge[j].w;

for i:=1 to n do if d[i]=inf then
writeln(start, '->', i, '=', 'Not')
else writeln(start, '->', i, '=', d[i]);
end;
{основной блок программы}
begin
clrscr;
write('Количество вершин > '); read(n);
e:=1;

for i:=1 to n do
for j:=1 to n do
begin
write('Вес ', i, '->', j, ' > '); read(w);
if w<>0 then
begin
edge[e].v:=i;
edge[e].u:=j;
edge[e].w:=w;
e:=e+1;
end;
end;

write('Стартовая вершина > '); read(start);
writeln('Список кратчайших путей:');
FB(n, start);
end.

 

Здесь граф представлен упрощенным списком ребер, который формируется по мере ввода пользователем матрицы весов. Основная часть алгоритма Беллмана – Форда (проверка условия) выполняется m*(n-1) раз, т. к. число повторений внешнего цикла равно n-1, а внутреннего – m. Отказ от n-ой итерации целесообразен, поскольку алгоритм справляется со своей задачей за n-1 шаг, но запуск внешнего цикла n раз позволит выявить наличие отрицательного цикла в графе. Проверить это можно, например, при помощи следующей модификации:

 

1
2
3
4
5
6
7
8
9
10
11
12
bool x=true;
for (i=0; i<n; i++)
{
if (i!=n-1)
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;
if (i==n-1)
for (j=0; j<e; j++)
if (d[edge[j].v]+edge[j].w<d[edge[j].u]) x=false;
}
if (!x) cout<<endl<<"Граф содержит отриц. циклы"<<endl;

 

Здесь внешний цикл выполняется n раз (в C++ принято начальным указывать значение 0, поэтому для данного кода n-1 раз), и если на n-ой стадии будет возможно улучшение, то это свидетельствует о наличие отрицательного цикла.

9 комментариев

Перейти полю для комментария

  1. kot

    За статью спасибо, но код на Си++, простите, ужасный. да и не Си++ это, а скорее Си. Вот реализация на Си++, основанная на коде из статьи: http://yadi.sk/d/S8Yz4Th9DNwVQ
    Можете включить в статью, если хотите.
    И с капчей у вас что-то: Всегда просит ввести результат 9 — ? = 2, но в итоге какое бы число не ввел(и 7 в том числе), всегда говорит, что капча неправильная.

    1. А. С. Третьяков

      Нельзя поконкретней, что именно в нем вас смутило? Вот основной фрагмент алгоритма:

      1
      2
      3
      4
      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;

      Какие здесь (или в другом месте) строчки стоит пересмотреть? Ваш код, конечно, содержит больше оператор, характерных именно для C++, но это делает его менее понятным.
      Капчу проверил — работает.

  2. xbron25

    Добрый день! Использовал алгоритм на языке Паскаль, статья отличная, но вопрос вот в чем:
    1)Не могли бы вы помочь реализовать этот код в случае ввода отрицательных весов ребер
    2)Если граф неориентированный и в случае , если буду брать веса ребер из матрицы смежности, а там ноль либо пустое значение, то что будет в этом случае ?
    Заранее благодарен за ответ, еще раз статья самая лучшая, что я нашел в интернете
    З.Ы. А я искал ооооочень много и долго ))

    1. А. С. Третьяков

      Здравствуйте. Данный код работает с отрицательными ребрами. Наверно вы задействовали неориентированное отрицательное ребро, в таком случае выходные данные могут оказаться неверными, поскольку он воспринимает такое ребро как отрицательный цикл, а сам алгоритм Беллмана-Форда с таковыми не работает. А что касается вашего второго вопроса, то тут все просто. Если вы указываете в качестве веса w ребра (v, u) значение 0, тогда это означает что v и u это одна и та же вершина, либо разные, но напрямую несвязанные ребром. Последний случай можно назвать ситуацией, когда указывается пустое значение.

      1. xbron25

        Действительно не подумал, а для неориентированного графа не могли бы вы помочь? Дело в том, что я взял алгоритм на паскаль, переделал для Дельфи , но работать она так как на паскале, отказывается! Вот и прошу помощи реализовать на дельфи во всех случаях для неориентированного графа пожалуйста! )

        1. А. С. Третьяков

          Он работает с неориентированными графами, но без отрицательных циклов — условие его работы. На Delphi ни разу не писал, но вроде обычный код паскаля должен работать и там. Могу предложить, то что нашел в интернете:

          1
          2
          3
          4
          5
          6
          7
          8
          9
          10
          11
          12
          13
          14
          15
          16
          17
          18
          19
          20
          21
          22
          23
          24
          25
          26
          27
          28
          29
          30
          31
          32
          33
          34
          35
          36
          37
          38
          39
          40
          41
          42
          43
          44
          45
          46
          const
            inf = $7FFFFFFF;
          type
            TEdge = record
              from: integer;
              to1: integer;
              l: integer;
            end;
          var
            n, m, i, j, v: integer;
            t: array [0 .. 1000] of longint;
            edges: array [0 .. 10000] of TEdge;
          begin
            read(n);
            readln(m);
            for i := 0 to m - 1 do
            begin
              read(edges[i].from, edges[i].to1);
              readln(edges[i].l);
              dec(edges[i].from);
              dec(edges[i].to1);
            end;
            readln(v);
            dec(v);
            for i := 0 to n - 1 do
              t[i] := inf;
            t[v] := 0;
            for i := 1 to n do
              for j := 0 to m - 1 do
                if (t[edges[j].from] < inf) and
                  (t[edges[j].from] + edges[j].l < t[edges[j].to1]) then
                  if i = n then
                  begin
                    writeln('INCORRECT INPUT');
                    exit;
                  end
                  else
                    t[edges[j].to1] := t[edges[j].from] + edges[j].l;
            for i := 1 to n - 1 do
            begin
              if (t[i] = inf) then
                writeln('NO')
              else
                writeln(t[i]);
            end;
          end.
          1. xbron25

            На совсем понятен код без комментариев )

  3. xbron25

    А в вашей программе , где вводиться вес ребра, то есть из i -> j , нужно ввести w-вес, а если он не равен 0, то что происходит?

    1. А. С. Третьяков

      Если вес ребра не равен нулю и в графе нет отрицательных циклов, то программа должна работать нормально.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Вы можете использовать эти теги HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Проверка на человечность *