Графы.Нахождение кратчайшего расстояния между двумя вершинами с помощью алгоритма Форда-Беллмана

Подробности

Категория: Сортировка и поиск

Алгоритм Беллмана–Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| ? |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана–Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.

Алгоритмы и структуры данных, 2 семестр, лекция 1

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

Лекция 3: Алгоритмы и методы поиска кратчайшего пути в графе 

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

Лекция 4: Матрицы. Поиск кратчайших путей в графах

Реализация алгоритма на различных языках программирования:

С++

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

kvodo

 Pascal

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.

kvodo