Структуры данных и алгоритмы (1021739), страница 48
Текст из файла (страница 48)
6.8. Здесь этот путь сначала идет к вершине w,затем возвращается к вершине х, принадлежащей предыдущему множеству S, затемследует к вершине v. Но реально такого кратчайшего пути не может быть. Поскольку вершина х помещена в множество S раньше вершины w, то все кратчайшие путиот источника к вершине х проходят исключительно через вершины предыдущегомножества 5.
Поэтому показанный на рис. 6.8 путь к вершине х, проходящий черезвершину w, не короче, чем путь к вершине х, проходящий через вершины множестваS. В результате и весь путь к вершине v, проходящий через вершины х и w, не короче, чем путь от источника к вершине х, проходящий через вершины множества S, идалее непосредственно к вершине и. Таким образом, доказано, что оператор в строке(8) листинга 6.3 действительно вычисляет длину кратчайшего пути.Предыдущее множество SРис.
6.8. Реально невозможныйкратчайший особый путь190ГЛАВА 6. ОРИЕНТИРОВАННЫЕ ГРАФЫВремя выполнения алгоритма ДейкстрыПредположим, что процедура листинга 6.3 оперирует с орграфом, имеющим пвершин и е дуг. Если для представления орграфа используется матрица смежности,то для выполнения внутреннего цикла строк (7) и (8) потребуется время О(л), а длявыполнения всех п - 1 итераций цикла строки (4) потребуется время порядка О(п2).Время, необходимое для выполнения оставшейся части алгоритма, как легко видеть,не превышает этот же порядок.Если количество дуг е значительно меньше л2, то лучшим выбором для представления орграфа будут списки смежности, а для множества вершин V \ S — очередь сприоритетами, реализованная в виде частично упорядоченного дерева.
Тогда времявыбора очередной вершины из множества V \ S и пересчет стоимости путей для одной дуги составит O(logn), а общее время выполнения цикла строк (7) и (8) —О(е logn), а не О(л2).Строки (1) - (3) выполняются за время порядка О(л). При использовании очередей с приоритетом для представления множества V \ S строка (5) реализуется посредством оператора DELETEMIN, а каждая из п - 1 итераций цикла (4) - (6) требует времени порядка O(logn).В результате получаем, что общее время выполнения алгоритма Дейкстры ограничено величиной порядка О(с logn). Это время выполнения значительно меньше,чем О(л2), когда е существенно меньше л2.6.4.
Нахождение кратчайших путей между парамивершинПредположим, что мы имеем помеченный орграф, который содержит время полета по маршрутам, связывающим определенные города, и мы хотим построить таблицу, где приводилось бы минимальное время перелета из одного (произвольного) города в любой другой. В этом случае мы сталкиваемся с общей задачей нахождениякратчайших путей, т.е. нахождения кратчайших путей между всеми парами вершин орграфа. Более строгая формулировка этой задачи следующая: есть ориентированный граф G = (V, £), каждой дуге v — > w этого графа сопоставлена неотрицательная стоимость C[v, w]. Общая задача нахождения кратчайших путей заключается внахождении для каждой упорядоченной пары вершин (v, w) любого пути от вершиныv в вершины w, длина которого минимальна среди всех возможных путей от v к w.Можно решить эту задачу, последовательно применяя алгоритм Дейкстры длякаждой вершины, объявляемой в качестве источника.
Но существует прямой способрешения данной задачи, использующий алгоритм Флойда (R. W. Floyd). Для опрётделенности положим, что вершины графа последовательно пронумерованы от 1 до л.'Алгоритм Флойда использует матрицу А размера л х л, в которой вычисляются длины кратчайших путей. Вначале A[i, j] = C[i, j] для всех i * j.
Если дуга i -» j отсутствует, то C[i, }] = °°. Каждый диагональный элемент матрицы А равен 0.Над матрицей А выполняется л итераций. После k-u итерации A[i, j] содержитзначение наименьшей длины путей из вершины i в вершину j, которые не проходят через вершины с номером, большим k. Другими словами, между концевымивершинами пути i и j могут находиться только вершины, номера которых меньшеили равны k.На fe-й итерации для вычисления матрицы А применяется следующая формула:А„[1,Л =Нижний индекс k обозначает значение матрицы А после fe-й итерации, но это неозначает, что существует л различных матриц, этот индекс используется для сокращения записи. Графическая интерпретация этой формулы показана на рис.
6.9.6.4. НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ МЕЖДУ ПАРАМИ ВЕРШИН191Рис. 63. Включение вершины kв путь от вершины i к вершине jРис. 6.10. Помеченный ориентированный графДля вычисления Ak[i, j] проводится сравнение величины Ak-i[i, f] (т.е. стоимостьпути от вершины i к вершине j без участия вершины k или другой вершины с болеевысоким номером) с величиной At_i[(, k] + At-.J_k, f] (стоимость пути от вершины i довершины А плюс стоимость пути от вершины А до вершины j ) . Если путь через вершину k дешевле, чем Ak-i[i, f], то величина A*[i, f] изменяется.Пример 6.8.
На рис. 6.10 показан помеченный орграф, а на рис. 6.11 — значенияматрицы А после трех итераций. П12303ОО8025103802A,[i, Л5801203573580023оо3580123ООAdi. Л12310352802А2Ц, Л02[i. ЛРис. 6.11. Последовательные значения матрицы АРавенства Ak\i, A] = At-i[i, А] и А4[А, у] = A^fA, у] означают, что на А-й итерацииэлементы матрицы А, стоящие в А-й строке и А-м столбце, не изменяются.
Более того,все вычисления можно выполнить с применением только одной копии матрицы А.Процедура, реализующая алгоритм Флойда, представлена в следующем листинге.Листинг 6.4. Реализация алгоритма Флойдаprocedure Floyd { var A: array[l..n, l..n] of real;C: arrayfl..n, 1..л] of real);vari, j, k: integer;beginfor i:= 1 to л dofor j:= 1 to n dofor i:= 1 to л doA[i, i]:= 0;for k:= 1 to л dofor i:= 1 to л dofor j:= 1 to л doif A[i, k] + A[k, j] < A(i, j] -thenA[i, j]: = A[i, k] + A[k, j]end; { Floyd }192ГЛАВА 6. ОРИЕНТИРОВАННЫЕ ГРАФЫВремя выполнения этой программы, очевидно, имеет порядок О(п3), поскольку вней практически нет ничего, кроме вложенных друг в друга трех циклов. Доказательство "правильности" работы этого алгоритма также очевидно и выполняется спомощью математической индукции по k, показывая, что на ft-й итерации вершина kвключается в путь только тогда, когда новый путь короче старого.Сравнение алгоритмов флойда и ДейкстрыПоскольку версия алгоритма Дейкстры с использованием матрицы смежности находит кратчайшие пути от одной вершины за время порядка О(п2), то в этом случаеприменение алгоритма Дейкстры для нахождения всех кратчайших путей потребуетвремени порядка О(п3), т.е.
получим такой же временной порядок, как и в алгоритмеФлойда. Константы пропорциональности в порядках времени выполнения для обоихалгоритмов зависят от применяемых компилятора и вычислительной машины, атакже от особенностей реализации алгоритмов. Вычислительный эксперимент и измерение времени выполнения — самый простой путь подобрать лучший алгоритмдля конкретного приложения.Если е, количество дуг в орграфе, значительно меньше, чем п2, тогда, несмотря наотносительно малую константу в выражении порядка О(п3) для алгоритма Флойда,мы рекомендуем применять версию алгоритма Дейкстры со списками смежности. Вэтом случае время решения общей задачи нахождения кратчайших путей имеет порядок О(пе logn), что значительно лучше алгоритма Флойда, по крайней мере длябольших разреженных графов.Вывод на печать кратчайших путейВо многих ситуациях требуется распечатать самый дешевый путь от однойвершины к другой.
Чтобы восстановить при необходимости кратчайшие пути,можно в алгоритме Флойда ввести еще одну матрицу Р, в которой элемент P[i, j]содержит вершину k, полученную при нахождении наименьшего значения A[i, j].Если P[i, j] = О, то кратчайший путь из вершины i в вершину j состоит из однойдуги i —> j. Модифицированная версия алгоритма Флойда, позволяющая восстанавливать кратчайшие пути, представлена в листинге 6.5.Листинг 6.5.
Программа нахождения кратчайших путейprocedure Floyd ( var A: array[l..n, l..n] of real;C:array[l..n, l . . n ] of real; P:array[1..n, l . . n ] of integer);vari, j, k: integer;beginfor i : = 1 to n dofor j:= 1 to n do beginA[i, j]:= C[i, j];P[i, j]:= 0end;for i:= 1 to л doA[i, i]:= 0;for k:= \ to n dofor i:= 1 to n dofor j:= 1 to л doif A[i, k] + A[k, j] < A[i, j] then beginA[i, j]:= A[i, k] + A[k, j];P(i, j]:= kendend; { Floyd }6.4. НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ МЕЖДУ ПАРАМИ ВЕРШИН193Для вывода на печать последовательности вершин, составляющих кратчайшийпуть от вершины i до вершины /, вызывается процедура path(i, j ) , код которой приведен в листинге 6.6.Листинг 6.6.
Процедура печати кратчайшего путиprocedure path ( i, j: integer ) ;vark: integer;begin*:= PU, j ] ;if k = 0 thenreturn;pathd, k) ;writeln(k);path(k, j )end; { path }Пример 6.9. На рис. 6.12 показана результирующая матрица Р для орграфа изрис. 6.10. D123130020100320Рис. 6.12. Матрица Р для орграфа из рис. 6.10Транзитивное замыканиеВо многих задачах интерес представляет только сам факт существования пути,длиной не меньше единицы, от вершины i до вершины ;'.
Алгоритм Флойда можноприспособить для решения таких задач. Но полученный в результате алгоритм ещедо Флойда разработал Уоршелл (S. Warshall), поэтому мы будем называть его алгоритмом Уоршелла.Предположим, что матрица стоимостей С совпадает с матрицей смежности дляданного орграфа G, т.е. C[i, f] = 1 только в том случае, если есть дуга i - » j , иC[i, Л ~ 0, если такой дуги не существует. Мы хотим вычислить матрицу А такую,что A[i, j] = 1 тогда и только тогда, когда существует путь от вершины i до вершиныj длиной не менее 1 и A[i. f] = 0 — в противном случае. Такую матрицу А часто называют транзитивным замыканием матрицы смежности.Пример 6.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
