Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 141
Текст из файла (страница 141)
Следовательно, г( [и] = б (з, и), что противоречит нашему выбору вершины и. Приходим к выводу„что во время добавления вершины и в множество Я выполняется равенство Н [и] = б (з, и), а следовательно, оно выполняется и в дальнейшем. Завершение. По завершении работы алгоритма выполняется равенство Я = $. Из этого равенства и инварианта Я = У вЂ” 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я У), не увеличивая при этом амортизированное время операции Ехтклст Мпч, позволяет получить реализацию, которая в асимптотическом пределе работает быстрее, чем реализация с помощью бинарных пирамид. Алгоритм Дейкстры имеет некоторую схожесть как с поиском в ширину (см.
раздел 22.2), так и с алгоритмом Прима, предназначенным для построения минимальных остовных деревьев (см. раздел 23.2). Поиск в ширину он напоминает в том отношении, что множество Е соответствует множеству черных вершин, используемых при поиске в ширину; точно так же, как вершинам множества Я сопоставляются конечные веса кратчайших путей, так и черным вершинам при поиске в ширину сопоставляются правильные расстояния.
На алгоритм Прима алгоритм Дейкстры похож в том отношении, что в обоих этих алгоритмах с помощью неубывающей очереди с приоритетами находится "самая легкая" вершина за пределами заданного множества (в алгоритме Дейкстры это множество 5, а в алгоритме Прима — "выращиваемое" дерево), затем эта вершина добавляется в множество, после чего соответствующим образом корректируются и упорядочиваются веса оставшихся за пределами множества вершин. 686 Часть Ч1 Алгоритмы для работы с графами Упражнения 24.3-1. Выполните алгоритм Дейкстры над ориентированным графом, изобра- женным на рис. 24.2.
Рассмотрите два варианта задачи, в одном из которых истоком является вершина з, а в другом — вершина з. Используя в качестве образца рис. 24.6, укажите, чему будуг равны значения И и я, и какие вершины будут входить в множество Я после каждой итерации цикла згИ!е. 24.3-2. Приведите простой пример ориентированного графа с отрицательными весами ребер, лля которого алгоритм Дейкстры дает неправильные ответы. Почему доказательство теоремы 24.6 не годится, если веса ребер могут быть отрицательными? 24.3-3. Предположим, что строка 4 алгоритма Дейкстры изменена следующим образом: 4 зчЫ!е )ф > 1 В результате этого изменения цикл згЬПе выполняется ٠— 1 раз, а не ~Ц раз.
Корректен ли предложенный алгоритм? 24.3-4. Пусть дан ориентированный граф С = (К Е), с каждым ребром (и, е) ЕЕ которого связано значение г (и, е), являющееся действительным числом в интервале О < г (и, с) < 1, и представляющее надежность соединительного кабеля между вершиной и и вершиной е. Величина г (и, е) интерпретируется как вероятность того, что в канале, соединяющем вершины и и е, не произойдет сбой; при этом предполагается, что все вероятности независимы. Сформулируйте эффективный алгоритм, позволяющий найти наиболее надежный путь, соединяющий две заданные вершины.
24.3-5. Пусть С = (Ъ; Е) — взвешенный ориентированный граф с весовой функ- цией ш: Š— (1, 2,..., И'), где И' — некоторое положительное целое число. Ни для каких двух вершин кратчайшие пути, ведущие из истока а в эти вершины, не имеют одинаковые веса. Предположим, что определен невзвешенный ориентированный граф С' = 1~" 0 1г', Е'), в котором каждое ребро (и, е) е Е заменяется и (и, с) последовательными ребрами единичного веса. Сколько вершин содержит граф С'? Теперь предположим, что в графе С' выполняется поиск в ширину. Покажите, что порядок, в котором вершины множества 1" окрашиваются в черный цвет при поиске в ширину в графе С', совпадает с порядком извлечения вершин множества Ъ' из очереди с приоритетами в строке 5 при выполнении алгоритма Ппкзткл над графом С.
24.3-6. Пусть С = (1г, .Е) — взвешенный ориентированный граф с весовой функ- цией ю: Е -~ (О, 1,..., И~), где И" — некоторое целое неотрицательное число. Модифицируйте алгоритм Дейкстры таким образом, чтобы он 687 Глава 24. Кратчайшие пути иэ одной вершины находил кратчайшие пути из заданной вершины в в течение времени 0 (И~Ъ'+ Е). 24.3-7. Модифнцируйте алгоритм из упражнения 24.3-6 таким образом, чтобы он выполнялся за время 0 ИУ+ Е) 18 И').
(Указание: сколько различных оценок кратчайших путей для вершин из множества У вЂ” Я может встретиться одновременно?) 24.3-8. Предположим, что имеется взвешенный ориентированный граф С = = (Ъ', Е), в котором веса ребер, исходящих из некоторого истока в, могут быть отрицательными, веса всех других ребер неотрицательные„и циклы с отрицательными весами отсутствуют. Докажите, что в таком графе алгоритм Дейкстры корректно находит кратчайшие пути из истока в.
24.4 Разностные ограничения и кратчайшие пути В главе 29 изучается общая задача линейного программирования, в котором нужно оптимизировать линейную функцию, удовлетворяющую системе линейных неравенств. В этом разделе исследуется частный случай задачи линейного программирования, который сводится к поиску кратчайших путей из одной вершины. Полученную в результате задачу о кратчайших путях из одной вершины можно решить с помощью алгоритма Беллмана-Форда, решив таким образом задачу линейного программирования. Линейное программирование В общей задаче линейного программирования (11пеаг-ргойгаппп)п8 ргоЫеш) задается матрица А размером гп х и, пз-компонентный вектор Ь и и-иэмпонентный вектор с.
Нужно найти состоящий из и элементов вектор х, максимизирующий целевую функцию (оЬ)есйче Йпсйоп) 2 „', с;х;, на которую накладывается гп ограничений Ах < Ь. Несмотря на то, что время работы симплекс-алгоритма, который рассматривается в главе 29, не всегда выражается полиномиальной функцией от размера входных данных, существуют другие алгоритмы линейного программирования с полиномиальным временем работы. Имеется ряд причин, по которым важно понимать, как устроены задачи линейного программирования.
Во-первых, если известно, что данная задача приводится к задаче линейного программирования с полиномиальным размером, то отсюда непосредственно следует, что для такой задачи существует алгоритм с полиномиальным временем работы. Во-вторых, имеется большое количество частных случаев задач линейного программирования, для которых существуют более производительные алгоритмы. Например, 688 в настоящем разделе показано, что задача о кратчайших путях из заданного истока — именно такой частный случай.
К другим задачам, которые можно привести к задачам линейного программирования, относятся задача о кратчайшем пути между парой заданных вершин (упражнение 24.4-4) и задача о максимальном потоке (упражнение 26.1-8). Иногда не имеет значения, какой должна получиться целевая функция; достаточно найти произвольное допустимое реиюеиие (геаз(Ые зо!щюп), т.е.
любой вектор х, удовлетворяющий неравенству Ах < Ь, или определить, что допустимых решений не существует. Сосредоточим внимание на таких зидачох существования (ГеаяЬ1!йу ргоЫеш). Системы разностных ограничений В системе разностпых ограничений (зуз!еш ог" ййегелсе солзггппГз) каждая строка в матрице линейного программирования А содержит одно значение 1 и одно значение — 1, а все прочие элементы в этой строке равны О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
