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

(

Определение

Bellman-Ford)

Алгоритм Беллмана-Форда позволяет решать задачу одного источника для взвешенного (графа) орграфа. Алгоритм работает при отрицательных весах дуг и, кроме того, определяет цикл отрицательного веса.

Атрибуты

В орграфе D=(V,A) задана вершина-источникs. Для каждой вершиныvVустанавливаются следующие аттрибуты:

• d[v] –верхняя граница весакратчайшего пути междуsиv;

• π[u] –вершина-предшественник (вершинаuявляется последней вершиной, из которой путь пришел в вершинуv).

Релаксация

Процесс релаксации аналогичен процессу, применяемому в алгоритме Дейкстры.

Очередь

Алгоритм устанавливает очередь FIFOдуг (первым пришел – первым вышел). Вершины ставятся в очередь случайным образом, поэтому не требуются сведения о расстоянияхd[u].

Итерации

Алгоритм Беллмана-Форда выполняется в общем случае за |V|-1 итераций.

Инициализация:

d[s]=0,d[v]=π[v]=nilдля всехvV-s.

При i=1 доi-|V|-1

Делать для каждой дуги {u,v} изFIFOочереди

Делать

Если d[u]+w(u,v)<d[v], тогда

d[v]= d[u]+w(u,v);

π[v]=u.

Определение циклов отрицательного веса:

Для каждой дуги {u,v}A

Делать

Если d[v]>d[u]+w(u,v), то возвратитьFALSE,

Иначе TRUE

Псевдокод

Сложность алгоритма Беллмана-Форда – О(mn),n=|V|,m=|A|.

FIFOочередь дуг (случайно построенная)

{d,c},{e,d},{b,e},{b,d},{d,b},{b,c},{s,c},{s,b}

FIFOочередь дуг (случайно построенная)

{b,d},{b,e},{e,d},{{d,c},d,b},{b,c},{s,c},{s,b}

3.6.3. Алгоритм Флойда (Floyd)

Определения

Алгоритм Флойда находит кратчайшие пути между всеми парами взвешенного графа или орграфа.

Алгоритм Флойда оперирует с матрицей весов[W(i,j)], которая является разновидностью взвешенной матрицы связности:

0 при i=j;

w(v_i,v_j), если есть ребро (дуга)из вершиныv_iв вершинуv_j;

в остальных случаях;

[W(i,j)]=

где w(v_i,v_j) – вес ребра (дуги) { v_i,v_j };

- знак бесконечности.

В течении kпроходов справедлива следующай формула:

W(i,j)=min {W(i,j),W(i,k)+W(k,j)},

которая означает, что если путь через V(k) является кратчайшим, то он и выбирается.

Для k=1 доnделать

Для j=1 доnделать

Для i=1 доnделать

S=W(i,k)+W(k,j);

Если S<W(i,j) , тогда

Конец jцикла;

Конец kцикла.