Алгоритмы - построение и анализ (1021735), страница 139
Текст из файла (страница 139)
(Во время первой итерации этого цикла и = е.) Таким образом, вершина и имеет минимальную оценку кратчайшего пути среди всех вершин множества У вЂ” Я. Затем строках 7-8 ослабляются все ребра (и, и), исходящие из вершины и. Если текущий кратчайший путь к вершине и может быть улучшен в результате прохождения через вершину и, выполняется ослабление и соответствующее обновление оценки величины Н [и] и предшественника х [и]. Обратите внимание, что после выполнения строки 3 вершины никогда не добавляются в множество Я и что каждая вершина извлекается из этого множества и добавляется в множество Я ровно по одному разу, поэтому количество итераций цикла ттЫ1е в строках 4-8 равно [У[.
Поскольку в алгоритме Дейкстры из множества У вЂ” Я для помещения в множество Я всегда выбирается самая "легкая" или "близкая" вершина, говорят, что этот алгоритм придерживается жадной стратегии. Жадные стратегии подробно описаны в главе 1б, однако для понимания принципа работы алгоритма Дейкстры читать эту главу не обязательно. Жадные стратегии не всегда приводят к оптимальным результатам, однако, как видно из приведенной ниже теоремы и следствия из нее, алгоритм Дейкстры действительно находит кратчайшие пути. Основное— показать, что после каждого добавления вершины и в множество Я выполняется равенство И [и] = б (е, и). Теорема 24.6 (Корректность алгоритма Дейкстры). По завершении обработки алгоритмом Дейкстры взвешенного ориентированного графа С = (У, Е) с неотрицательной весовой функцией ш и истоком е для всех вершин и е У выполняется равенство И[и] = б(а,и).
Часть Ч1. Алгоритмы для работы с графами 682 Рис. 24.б. Выполнение алгоритма Дейкстры Доказагаельсгаво. Воспользуемся сформулированным ниже инвариантом цикла. В начале каждой итерации цикла Ми!е в строках 4-8 для каждой вершины и Е 5 выполняется равенство Н [и] = б (з, и). Достаточно показать, что для каждой вершины и е И равенство Ы [и] = б (з, и) выполняется в момент ее добавления в множество Я. После того как будет показана справедливость равенства И [и] = б (з, и), на основе свойства верхней границы мы покажем, что это равенство продолжает выполняться и в дальнейшем. Инициализации. Изначально выполняется равенство Я = Э, поэтому справедли- вость инварианта очевидна.
Сохранение. Нужно показать, что при каждой итерации равенство й [и] = б (з, и) выполняется для каждой вершины, добавленной в множество Я. Воспользуемся методом "от противного". Чтобы получить противоречие, предположим, что и — первая добавленная в множество Я вершина, для которой д [и] Ф б (з, и). Сосредоточим внимание на ситуации, сложившейся в начале той итерации цикла зтййе, в которой вершина и добавляется в множество Я. Проанализировав кратчайший путь из вершины з в вершину и, можно будет получить противоречие, заключающееся в том, что на тот момент справедливо равенство И [и] = б (з, и). Должно выполняться условие и ф з, поскольку з — первая вершина, добавленная в множество Я, и в момент ее добавления выполняется равенство Н [з] = б (з, з).
Из условия и ф з следует также, что непосредственно перед добавлением вершины и в множество Я оно не является пустым. Из вершины з в вершину и должен вести какой- нибудь путь, так как в противном случае, в соответствии со свойством отсутствия пути, выполняется соотношение г2 [и] = б (з, и) = оо, нарушающее Глава 24.
Кратчайшие пути из одной вершины 683 Рис. 24.7. Иллюстрация к доказа- тельству теоремы 24.6 справедливость предположения, что Й [и] Ф д(в, и). Поскольку хоть один путь существует„то должен существовать и кратчайший путь р из вершины в в вершину и. Перед добавлением вершины и в множество Я путь р соединяет вершину из множества 5 (вершнну в) с вершиной из множества 'Р' — 5 (вершнну и). Рассмотрим первую вершину у на пути р, принадлежащую множеству Р' — 5, а также предположим, что ей предшествует вершина х Е 5. Тогда, как видно из рис.
24.7, путь р можно разложить на составляРг Рг ющие в - х — у - и. (Любой из путей рг и рз может не содержать ни одного ребра.) В примере, приведенном на рисунке, множество Я непосредственно перед добавлением в него вершины и не является пустым. Кратчайший путь р из Рг Рг истока в в вершину и раскладывается на составляюшие в - х — у - и, где у — первая вершина на пути, не принадлежащая множеству Я, а вершина х е Я расположена непосредственно перед вершиной у. Вершины х и у не совпадают, однако возможен случай, когда в = х или у = и. Путь рз может возвращаться в множество Я (но может и не возвращаться). Мы утверждаем, что когда вершина и добавляется в множество Я, выполняется равенство Ы [у] = Б (в, у).
Чтобы доказать это утверждение, заметим, что х е Я. Далее, поскольку вершина и выбрана как первая вершина, после добавления которой в множество Я выполняется соотношение И [и) ~ ф б (в, и), то после добавления вершины х в множество Я справедливо равенство гг [х) = Б(в,х). В это время (т.е. при добавлении вершины и в множество Я) происходит ослабление ребра (х, у)„поэтому сформулированное выше утверждение следует из свойства сходимости.
Теперь можно получить противоречие, позволяющее доказать, что 0 [и) = = б (в, и). Поскольку на кратчайшем пути из вершины в в вершину и вершина у находится перед вершиной и, и вес каждого из ребер выражается неотрицательным значением (это особенно важно для ребер, из которых состоит путь рз), выполняется неравенство д (в, у) < д (в, и), поэтому 0[у] = Б(в,у) < б(в,и) < й[и], (24.2) Часть Ч1 Алгоритмы для работы с графами 684 где последнее неравенство следует из свойства верхней границы.
Однако поскольку и вершина и, и вершина у во время выбора вершины и в строке 5 находились в множестве )г — Я, выполняется неравенство Ы [и] < б [у]. Таким образом, оба неравенства в соотношении (24.2) фактически являются равенствами, т.е. И[у] = б(з,у) = б(з,и) = 0[и]. Следовательно, г( [и] = б (з, и), что противоречит нашему выбору вершины и. Приходим к выводу„что во время добавления вершины и в множество Я выполняется равенство Н [и] = б (з, и), а следовательно, оно выполняется и в дальнейшем. Завершение. По завершении работы алгоритма выполняется равенство Я = $.
Из этого равенства и инварианта Я = У вЂ” 5 следует, что Я = 'и". Таким образом, для всех вершин и е )Г выполняется равенство Ы [и] = б (з, и). ° Следствие 24.7. Если выполнить алгоритм Дейкстры для взвешенного ориентированного графа С = (К Е) с неотрицательной весовой функцией и и истоком з, то по завершении работы алгоритма подграф предшествования С является деревом кратчайших путей с корнем в вершине з. Доказательство. Сформулированное выше утверждение непосредственно следует из теоремы 24.6 и свойства подграфа предшествования.
В Анализ Насколько быстро работает алгоритм Дейкстры? В нем поддерживается неубывающая очередь с приоритетами Я и тремя операциями, характерными для очередей с приоритетами: 1мзект (явно вызывается в строке 3), Ехтклст Мпч (строка 5) и Рескелзе КеУ (неявно присутствует в процедуре КеьАх, которая вызывается в строке 8). Процедура 1мзект, как и процедура Ехтклст Мпч, вызывается по одному разу для каждой вершины. Поскольку каждая вершина и е )г добавляется в множество Я ровно по одному разу, каждое ребро в списке смежных вершин А4 [и] обрабатывается в цикле Гог, заданном в строках 7-8, ровно по одному разу на протяжении работы алгоритма.
Так как полное количество ребер во всех списках смежных вершин равно [Е], всего выполняется [Е] итераций этого цикла 1ог, а следовательно, не более [Е[ операций РЕСКЕАЯЕ КЕУ. (Еще раз заметим, что здесь используется групповой анализ.) Время выполнения алгоритма Дейкстры зависит от реализации неубывающей очереди с приоритетами. Сначала рассмотрим случай, когда неубывающая очередь с приоритетами поддерживается за счет того, что все вершины пронумерованы от 1 до Щ. Атрибут а'[и] просто помещается в элемент массива с индексом и.
Каждая операция 1мзеит и Рескелзе Кеу занимает время 0(1), а каждая Глава 24. Кратчайшие пути из одной вершины 685 операция Ехтклст Мпч — время О (У) (поскольку в ней производится поиск по всему массиву); в результате полное время работы алгоритма равно О (Уз + Е) = = О(Уз) Если граф достаточно разреженный, в частности, если количество вершин и ребер в нем связаны соотношением Е = о (Уз/1бУ), с практической точки зрения целесообразно реализовать неубывающую очередь с приоритетами в виде бинарной неубывающей пирамиды. (Как было сказано в разделе 6.5, важная деталь реализации заключается в том, что вершины и соответствующие им элементы пирамиды должны поддерживать идентификаторы друг друга.) Далее, каждая операция Ехтклст Мпч занимает время О (!к У). Как и раньше, таких операций 1Ц.
Время, необходимое для построения неубывающей пирамиды, равно О (У). Каждая операция Впскплзл Кну занимает время О (1к У), и всего выполняется не более ~Е1 таких операций. Поэтому полное время выполнения алгоритма равно О ((У + Е) 1к У), что равно О (Е 1к У), если все вершины достижимы из истока. Это время работы оказывается лучшим по сравнению со временем работы прямой реализации О (Уз), если Е = о (Уз/!б У). Фактически время работы алгоритма может достигать значения О(У )к У + Е), если неубывающая очередь с приоритетами реализуется с помощью пирамиды Фибоначчн (см. главу 20). Амортизированная стоимость каждой из 1Ц операций Ехтклст Мпч равна О (1я У), и каждый вызов процедуры Рнскплзн Кп' (всего не более 1Е1), занимает лишь О (1) амортнзированного времени. Исторически сложилось так, что развитие пирамид Фибоначчи было стимулировано наблюдением, согласно которому в алгоритме Дейкстры процедура Ркскплзк Кпу обычно вызывается намного чаще, чем процедура Ехтклст Мпч, поэтому любой метод, уменьшающий амортизированное время каждой операции Впскллзв Клу до величины о (1я У), не увеличивая при этом амортизированное время операции Ехтклст Мпч, позволяет получить реализацию, которая в асимптотическом пределе работает быстрее, чем реализация с помощью бинарных пирамид.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
