Первый этап.. Второй этап.. Первый этап.

⇐ ПредыдущаяСтр 4 из 5Следующая ⇒

Первый этап.

0-шаг (задание начального приближения)

W⁰(s):=0.

Для всех i Î E\{s} W⁰(i):=M (где M - достаточно большое число, например, большее, чем длина самого длинного пути).

j-ый шаг. ( j=1, 2, 3, ...)

W ^j(s)=:0 (7.6)

W^j(i) := min { c(v) + W^j-1(h2(v)) | v Î V ^-(i) } iÎE\{s} .

Если после двух следующих друг за другом итерациях j и (j+1)

W ^j(i)=W^j+1(i) для всех i Î E ,

то полагаем

W(i)=W ^j⁺¹(i) для всех iÎE.

Если W(t) ³ M, то задача не имеет решения (нет путей между вершинами t и s), в противном случае переходим к выполнению второго этапа.

Второй этап.

0-шаг i:=t.

j-ый шаг (j=1, 2, 3, ...),

v (j):=arg min { c(v) + W(h2(v)) | vÎV ^-( i (j-1) ) } (7.7)

i(j):=h2( v(j) )

Если i(j)=s, то алгоритм заканчивает работу, в противном случае переходим к (j+1) шагу.

Этот алгоритм можно модифицировать следующим образом. На первом этапе на каждом j-м шаге при вычислении W(i j) по соотношению (7.6) полагаем

v(i)=arg min { c(v) + W(h2(v)) | vÎV ^-(i) },

тогда на втором этапе соотношение (7.7) можно заменить следующим соотношением

v(j):=v(i(j-1).

7.4. Алгоритм Флойда для отыскания кратчайших расстояний на графе

Пусть W(i) – верхние оценки кратчайших расстояний от вершины i до вершины s. Если для любой дуги vÎV выполняется

W(h1(v))£ c(v) + W(h2(v)),

то оценки W(i) дают кратчайшие расстояния от вершины i до вершины s. Заметим, что если некоторая дуга vÎV содержится в кратчайшем пути из некоторой вершины i (например из вершины h1(v) ) в вершину s, то для нее

W(h1(v)) = c(v) + W(h2(v)).

Если существует дуга vÎV, для которой

W(h1(v)) > c(v) + W(h2(v)),

то оценки W(i) не дают кратчайшие расстояния от вершин i до вершины s, так как оценку W(h1(v)) можно улучшить, положив

W(h1(v)) = c(v) + W(h2(v)).

На этом свойстве основан алгоритм Флойда.

Первый этап.

0-шаг (задание начального приближения).

W(s):=0;

Для всех iÎE\{s} W(i):=M;

j-й шаг. ( j=1, 2, 3, ...)

Среди всех дуг vÎV ищем дугу, для которой

W(h2(v))<M, W(h1(v)) > c(v) + W(h2(v)).

Если такой дуги не существует, то переходим к выполнению второго этапа, в противном случае

W(h1(v)):= c(v)+W(h2(v))

и переходим к выполнению следующего шага.

⇐ Предыдущая 1 2 345 Следующая ⇒