Метод Форда


Рассмотрим ориентированную сеть G=(I,U) без контуров, с одним источником s и стоком t. Числа на дугах lij означают их длину. найдем следующим образом: источнику т.е. вершине 1 присваиваем метку Е1=0, число 0 означает, что это кратчайший путь до источника. Вершине 2 присваиваем метку Е21+l12 . Далее последовательно будем присваивать метки вершинам 3,4,…,n по правилу:

Еj=min(Ei+lij), j=3,4,…,n

{(i,j)}

{(i,j)}- означает множество дуг (i,j), входящих в вершину j. Число Ej равно длине кратчайшего пути от вершины s до вершины j.

Помечая вершины таким образом мы дойдем до стока. Метка Et и будет означать длину кратчайшего пути от источника до стока.

Если в сети надо найти длину максимального пути, то пометки вершин 1 и 2 расставляют аналогично, а метки каждой последующей вершины находят по формуле:

Еj=max(Ei+lij), j=3,4,…,n

{(i,j)}

Найдем кратчайший путь для нашего примера:

Е2=E1+l12=0+1=1

Определив пометки вершин, начиная со второй, будем помечать * дугу, для которой в формуле находится минимальное значение. В самом начале всегда помечаем * дугу(1,2).

Е3=min(0+2;1+3)=2 Метим * дугу (1,3) так как этой дуге соответствует min.

Е4=min(1+5;2+5)=6 Метим * дугу (2,4) так как этой дуге соответствует min.

Е5=min(2+12;6+7)=6 Метим * дугу (4,5) так как этой дуге соответствует min.

Е6=min(1+6;13+3)=7 Метим * дугу (4,6) так как этой дуге соответствует min.

Длина кратчайшего пути от 1 до 6 равна:

lmin=E6=7

Сам кратчайший путь найдем двигаясь с конца графика: от вершины 6 к началу графика – к вершине 1 вдоль помеченных * дуг в направлении, противоположном их ориентации.

lmin=(1,2,4,6)