Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 153
Текст из файла (страница 153)
Тогда веса присваивались бы ие ребрам, а вершинам. Модифицируйте процедуру ОАсЯноктпзт-Рятнз таким образом, чтобы оиа за линейное время позволяла найти самый длинный путь в ориентированном ациклическом графе со взвешенными вершинами. 24.2.4 Разработайте эффективный алгоритм, позволяющий определить общее количество путей, содержащихся в ориентированном ациклическом графе. Проаиализируйте время работы этого алгоритма. Часть 17.
Алгоритмы для работы с графами 696 24.3. Алгоритм Дейкстры Алгоритм Дейкстры решает задачу поиска кратчайших путей из одной вершины во взвешенном ориентированном графе С = (Ъ; Е) в случае, когда веса ребер неотрицательны. Поэтому в настоящем разделе предполагается, что для всех ребер (и, и) Е Е выполняется неравенство ю(и,и) > О. Через некоторое время станет понятно, что при хорошей реализации время работы алгоритма Дейкстры меньше времени работы алгоритма Беллмана — Форда. В алгоритме Дейкстры поддерживается множество вершин Я, для которых уже вычислены окончательные веса кратчайших путей к ним из истока л.
В этом алгоритме поочередно выбирается вершина и е Ъ' — Я, которой на данном этапе соответствует минимальная оценка кратчайшего пути. После добавления этой вершины и в множество Я проводится ослабление всех исходящих из нее ребер. В приведенной ниже реализации используется неубываю1цая очередь с приоритетами сг, состоящая из вершин, в роли ключей которых выступают значения их атрибутов с1. Р!ЖЗТКА(С, иг, л) 1 11ч171АС1хе-бпчсгее-бопксе(С, В) 2 3=1) 3 Я=С.)г 4 ч'п11е Я р В 5 и = Ехтклст-Мпч(Я) 6 Я = Я0(и) 7 1ог каждой вершины и Е С.Аф(и) 8 КЕСАХ(и, и, го) // С СООТВЕТСТВУЮЩИМИ ВЫЗОВВМИ ггЕСКЕАЗЕ-КЕУ Процесс ослабления ребер в алгоритме Дейкстры проиллюстрирован на рис.
24.6. В строке 1 выполняется обычная инициализация величин й и я, а в строке 2 инициализируется пустое множество вершин Я. В этом алгоритме поддерживается инвариант, согласно которому в начале каждой итерации цикла иййе в строках 4-8 выполняется равенство Я = Ъ' — Я. В строке 3 неубывающая очередь с приоритетами Ч инициализируется таким образом, чтобы она содержала все вершины множества Тг; поскольку в этот момент Я = й, после выполнения строки 3 сформулированный выше инвариант выполняется. На каждой итерации цикла и Ьйе в строках 4-8 в строке 5 вершина и извлекается из множества Я = )г — Я и добавляется в множество Я в строке 6, в результате чего инвариант продолжает соблюдаться.
(Во время первой итерации этого цикла и = В.) Таким образом, вершина и имеет наименьшую оценку кратчайшего пути среди всех вершин множества Ъ' — Я. Затем в строках 7 и 8 ослабляются все ребра (и, и), исходящие из вершины и. Если текущий кратчайший путь к вершине и может быть улучшен в результате прохождения через вершину и, выполняется ослабление и соответствующее обновление оценки и. 4 и предшественника и.я. Обратите внимание. 697 Глава 24. Кратчайшие пути нз одной еершнны х х 1 х ~ б: — —.~ ')4) Ю в — — — ьч (б) (в) (в) х ОО (в) (г) Рнс. 24.6.
Работа алгоритма Дейкстры. Истоком а является крайняя слева вершина. В вершинах показаны оценки кратчайших путей, а залприхованные ребра указывают предшественников. Черные вершины находятся в множестве Я, а белые — в неубывающей очереди с приоритетами (г = И вЂ” Я. (а) Ситуация непосредственно перел первой итерацией цикла мЫ1е в строках 4-8. Заштрихованная вершина имеет минимальное значение а' и выбирается в качестве вершины и в строке 5.
(6)-(е) Ситуация после каждой послелующей итерации цикла мЫ!е. В каждой части в очередной итерации в качестве вершины и в строке 5 выбирается заштрихованная вершина. Значения в( и предшественники, показанные в части (е), являются окончательными. что после выполнения строки 3 вершины никогда не добавляются в множество Я и что каждая вершина извлекается из этого множества и добавляется в множество Я ровно по одному разу, поэтому количество итераций цикла шЫ(е в строках 4-8 составляет в точности ~Ц. Поскольку в алгоритме Дейкстры из множества (У вЂ” Я для помещения в множество Я всегда выбирается самая "легкая", или "близкая", вершина, можно утверждать, что этот алгоритм придерживается жадной стратегии. Жадные стратегии подробно описаны в главе !6, однако для понимания принципа работы алгоритма Дейкстры читать эту главу необязательно.
Жадные стратегии не всегда приводят к оптимальным результатам, однако, как видно из приведенной ниже теоремы и следствия из нее, алгоритм Дейкстры действительно находит кратчайшие пути. Главное — показать, что после каждого добавления вершины и в множество Я выполняется равенспю и. (( = Ю(л, и). Теорема 24.6 (Корректность алгоритма Дейкстры) По завершении обработки алгоритмом Дейкстры взвешенного ориентированного графа (л = ((у, Е) с неотрицательной весовой функцией и) и истоком л для всех вершин и б (У выполняется равенство и. (( = б(л, и). Доказательство. Воспользуемся следующим инвариантом цикла: В начале каждой итерации цикла зчЬПе в строках 4-8 для каждой вершины и е Я выполняется равенство и.
(( = б(я, и). Часть Рй Алгоритмы блл работы с графами б98 ж ь, Рис. 24.7. Доказательство теоремы 24.6. Множество о перед добавлением в него вершины и непустое. Разделим кратчайший путь р из истока я к вершине и на я х — ь р 3 и, где у — первая Р1 л вершина на пути, не влодяшая в о, а х б о — непосредственный предшественник р. Вершины х и у различны, но может быть так, что в = х или у = и.
Путь рг может (необязательно) повторно входить в о. Достаточно показать, что для канадой вершины и е зг равенство и. Н = б(л, и) выполняется в момент ее добавления в множество Я. После того как будет показана справедливость равенства и. Н = б(л, и), на основе свойства верхней границьз мы покажем, что это равенство продолжает выполняться и в дальнейшем.
Инициализация, Изначально Я = з), тик что инвариант тривиально выполняется. Сохранение. Нужно показать, что при каждой итерации равенспю и. ь( = б(а, и) выполняется для каждой вершины, добавленной в множество Я. Воспользуемся методом "от противного". Чтобы получить противоречие, предположим, что и — первая добавленная в множество Я вершина, для которой и.
Ы ~ б(л, и). Сосредоточим внимание на ситуации, сложившейся в начале той итерации цикла зтпйе, в которой вершина и добавляется в множество Я. Проанализировав кратчайший путь из вершины я в вершину и, можно будет получить противоречие, заключающееся в том, что в тот момент справедливо равенство и.
д = б(я, и). Должно выполняться условие и уб я, поскольку я — первая вершина, добавленная в множество Я, и в момент ее добанления выполняется равенство я.Н = 6(л,л) = О. Из условия и ~ я следует также, что непосредственно перед добавлением вершины и в множество Я оно не является пустым. Из вершины а в вершину и должен вести какой-нибудь путь, так как в противном случае, в соответствии со свойством отсутствия пути, выполняется соотношение и. с( = д(а, и) = со, нарушающее справедливость предположения, что и. И Ф б(л, и).
Поскольку хоть один путь существует, должен существовать и кратчайший путь р из вершины я в вершину и. Перел добавлением вершины и в множество Я путь р соединяет вершину из множества Я (а именно — вершину я) с вершиной из множества И вЂ” Я (а именно— с вершиной и). Рассмотрим первую вершину у на пути р, принадлежащую множеству И вЂ” Я, а также предположим, что на этом пути ей предшествует вершина х Е Я. Тогда, как видно из рис. 24.7, путь р можно разложить на составляющие я» х -+ у и. (Любой из путей рз и рз может не содержать ии одного ребра.) Мы утверждаем, что у. И = б(л,п) при добавлении и в Я. Для доказательства этого утверждения заметим, что х е Я. Затем, поскольку мы выбираем как первую вершину для которой и.д уЬ б(а,и) при ее добавлении в Я. при тнава 24. Кратчайшие нута ив одной вершины б99 добавлении х в Я мы имеем х.6 = 6(в, х). Ребро (х, у) в этот момент было ослаблено, и наше утверждение вытекает из свойства сходимости.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
