Главная Промышленная автоматика.

Рис. 63. Включение вершины к в путь от вершины i к вершине j

Рис. 6.10. Помеченный ориентированный граф

Для вычисления проводится сравнение величины /] (т.е. стоимость

пути от верпгины i к верпгине / без участия верпгины к или другой верпгины с более высоким номером) с величиной Aj i[i, к] + At~\[k,f] (стоимость пути от верпгины i до верпгины А плюс стоимость пути от верпгины А до верпгины j). Если путь через вер-пгину к депгевле, чем Ai i[i,/7, то величина At[i, изменяется.

Пример 6.8. На рис. 6.10 показан помеченный орграф, а на рис. 6.11 - значения матрицы А после трех итераций. □

Adi. Л

Alii. Л

Azli.JI

А:,[1.Л

Рис. 6.11. Последовательные значения матрицы А

Равенства Aj[i, А] =Aj.-i[i, А] и Ац[, у] = Ai,-i[k,y} означают, что на А-й итерации элементы матрицы у1, стоящие в А-й строке и А-м столбце, не изменяются. Более того, все вьмисления можно выполнить с применением только одной копии матрицы А. Процедура, реализующая алгоритм Флойда, представлена в следующем листинге.

Листинг 6.4. Реализация алгоритма Флойда

procedure Floyd { var А: аггау[1..л, l..n] of real;

С: array[l..n, l..n] of real);

i, jr k: integer; begin

for i:= 1 to л do

for J:= 1 to n do

A[i. j]:= C{i, j]; for i:= 1 to л do

Л[1, il:= 0; for ;;::= 1 to л do

for i:= 1 to л do

for j:= 1 to л do

if A[i, k] + A[k, j] < A[i, j] : = A[i, k]

end; { Floyd }

A(i, j] then + A[k, j]



Время выполнения этой программы, очевидно, имеет порядок О(л), поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов. Доказательство "правильности" работы этого алгоритма также очевидно и выполняется с помощью математической индукции по к, показывая, что на ft-й итерации верпшна k включается в путь только тогда, когда новый путь короче старого.

Сравнение алгоритмов флойда и Дейкстры

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

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

Вывод на печать кратчайших путей

Во многих ситуациях требуется распечатать самый дещевый путь от одной верщины к другой. Чтобы восстановить при необходимости кратчайщие пути, можно в алгоритме Флойда ввести еще одну матрицу Р, в которой элемент P[i, j] содержит верщину к, полученную при нахождении наименьщего значения у4/г, . Если P[i,j] = О, то кратчайший путь из верщины i в верщину / состоит из одной дуги i -> j. Модифицированная версия алгоритма Флойда, позволяющая восстанавливать кратчайщие пути, представлена в листинге 6.5.

Листинг 6.5. Программа нахождения кратчайших путей

procedure Floyd ( ах А: array [1.. л, 1. . л] of real;

C:array[l. .n, 1..л] of real; P: array [ 1. . л, 1..л) of integer); var

i, j, k: integer; begin

for i:= 1 to n do

for J:= 1 to n do begin A[i, j] r=C[l, jl ; P[i, j] := 0

end;

for i;= 1 to л do

A[i, i] := 0; for k:= \ to n do

for i: = 1 to n do

for J:= 1 to л do

if A[i, k] + A[k, j] <A[i, j] then begin A[i, j] -•= A[i, k] +A[k, Jl ; P(i, j] -k

end; { Floyd }



Для вывода на печать последовательности вершин, составляющих кратчайший путь от вершины / до вершины /, вызывается процедура/>atA(i, у7, код которой приведен в листинге 6.6.

Листинг 6.6. Процедура печати кратчайшего пути

procedure path ( i, j: integer ) ; var

k: integer; begin

k:= Pli, j]; if к = 0 then return;

pathd, kj; writelnik) ; path(k, J) end; { path }

Пример 6.9. Ha рис. 6.12 показана результирующая матрица Р для орграфа из рис. 6.10. D

Рис. 6.12. Матрица Р для орграфа из рис. 6.10

Транзитивное замыкание

Во многих задачах интерес представляет только сам факт существования пути, длиной не меньше единицы, от вершины / до вершины j. Алгоритм Флойда можно приспособить для решения таких задач. Но полученный в результате алгоритм еще до Флойда разработал Уоршелл (S. Warshall), поэтому мы будем называть его алгоритмом Уоршелла.

Предположим, что матрица стоимостей С совпадает с матрицей смежности для данного орграфа G, т.е. C[i, j\ = 1 только в том случае, если есть дуга / -» и C[i, Л ~ О, если такой дуги не существует. Мы хотим вычислить матрицу А такую, что A[i, j] = 1 тогда и только тогда, когда существует путь от вершины / до вершины j длиной не менее 1 и A[i.fJ = О - в противном случае. Такую матрицу А часто называют транзитивным замыканием матрицы смежности.

Пример 6.10. На рис. 6.13 показано транзитивное замыкание матрицы смежности орграфа из рис. 6.10. D

Рис. 6.13. Транзитивное замыкание матрицы смежности

Транзитивное замыкание можно вычислить с помощью процедуры, подобной Floyd, применяя Hafe-мшаге следующую формулу к булевой матрице

A,[i.J] = At-i[j. /у or (AtiEi. А] and A4-i[ft.;]).





0 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 56 57 58 59 [60] 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0036