Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 154
Текст из файла (страница 154)
Теперь можно получить противоречие, позволяющее доказать, что и.6 6(в,и). Поскольку на кратчайшем пути из вершины в в вершину и верши- на у находится перед вершиной и и вес каждого из ребер выражается неот- рицательным значением (это особенно важно для ребер, нз которых состоит путь рз), выполняется неравенство 6(в, у) < 6(в, и), так что у.6 = 6(в,у) < 6(в,и) < и.6 (24.2) (согласно свойству верхней границы) . Однаю поскольку и вершина и, и вершина у во время выбора вершины и в строке 5 находились в множестве 12 — Я, выполняется неравенство и. 6 < у.
6. Таким образом, оба неравенства в соотношении (24.2) фактически являются равенствами, т.е. у.6 = 6(в,у) = 6(в,и) = и.6. Следовательно, и.6 = 6(в, и), что противоречит нашему выбору вершины и. Мы приходим к выводу, что во время добавления вершины и в множество Я выполняется равенство и.6 = 6(в,и), а следовательно, оно выполняется и в дальнейшем. Завершение.
По завершении работы алгоритма Я = й. Из этого факта и инварианта с2 = 'й — Я следует, что Я = 'й. Таким образом, для всех вершин и Е И выполняется равенство и. 6 = 6(в, и). Следсаввае 24. 7 Если выполнить алгоритм Дейкстры для взвешенного ориентированного графа С = (12 Е) с неотрицательной весовой функцией ш и истоюм в, то по завершении работы алгоритма подграф предшествования С является деревом кратчайших путей с корнем в вершине ж Анализ алгоритма Насколько быстро работает алгоритм Дейкстры? В нем поддерживается неубывающая очередь с приоритетами й4 и тремя операциями, характерными для очередей с приоритетами: 1нзект (явно вызывается в строке 3), ЕхткАст-Мпч (строка 5) и ПескеАБе-Кеу (неявно присутствует в процедуре КееАх, которая вызывается в строке 8).
Процедура 1нзект, как и процедура ЕхткАст-М1ы, вызывается по одному разу для каждой вершины. Поскольку каждая вершина и е 1е добавляется в множество Я ровно по одному разу, каждое ребро в списке смежности А62 1и) обрабатывается в цикле 1ог в строках? и 8 ровно по одному разу на протяжении работы алгоритма. Так как общее количество ребер во всех списках Доказалвепьсявео. Сформулированное выше утверждение непосредственно следует из теоремы 24.б и из свойства подграфа предшествования.
Часть гл Алгоритмы длл работы с графами смежности равно ~Е(, всего выполняется (Е( итераций этого цикла Гвг, а следовательно, не более (Е~ вызовов РискпАзи-КЕу. (Еще раз заметим, что здесь используется групповой анализ.) Время работы алгоритма Дейкстры зависит от реализации неубывающей очереди с приоритетами. Сначала рассмотрим случай, когда неубывающая очередь с приоритетами поддерживается за счет того, что все вершины пронумерованы от 1 до ~(г1 Атрибут о. й просто помещается в элемент массива с индексом о. Каждая операция 1изпкт и РескеАБе-Кеу занимает время 0(1), а каждая операция Ехтклст-М~м — время 0(Ъ') (поскольку в ней выполняется поиск по всему массиву); в результате полное время работы алгоритма равно 0(Ъ'з + Е) = 0(1'з).
Если граф достаточно разреженный, в частности, если количество вершин и ребер в нем связаны соотношением Е = о(1г~/1й И), алгоритм можно сделать более эффективным путем реализации неубываннцей очереди с приоритетами с помощью бинарной неубывающей пирамиды. (Как говорится в разделе 6.5, важная деталь реализации заключается в том, что вершины и соответствующие им элементы пирамиды должны поддерживать идентификаторы друг друга.) Каждая операция Ехтклст-Мпч занимает время О(1я И).
Как и ранее, всего таких операций — ~1г~. Время, необходимое для построения неубывающей пирамиды, равно 0((г). Каждая операция РкскпАзп-Клу выполняется за время 0(1кЪ'), а всего таких операций выполняется не более ~Е~. Поэтому полное время работы алгоритма составляет 0((Ъ' + Е) 1я И), что равно 0(Е1к(г), если все вершины достижимы из истока. Это время работы оказывается лучшим по сравнению со временем работы прямой реализации 0(Из), если Е = о(Ъ'з/1й $г).
Фактически можно достичь времени работы алгоритма 0(И 1я (г + Е), если неубывающая очередь с приоритетами реализуется с помощью фибоначчиевой пирамиды (см. главу 19). Амортизированная стоимость каждой из ~Ц операций ЕхткАст-Мпч равна 0(1к Ъ'), а каждый вызов процедуры РескеАБе-Кеу (всего их не более ~Е~) требует лишь 0(1) амортизированного времени. Исторически сложилось так, что развитие пирамид Фибоначчи было стимулировано наблюдением, согласно которому в алгоритме Дейкстры процедура РескеАБе-Кеу обычно вызывается намного чаще, чем процедура ЕхткАст-Мпч, поэтому любой метод, уменьшающий амортизированное время каждой операции РксккАзк-Кеу до величины о(1к )г'), не увеличивая при этом амортизированного времени операции ЕхткАст-Мпч, позволяет получить реализацию, которая в асимптотическом пределе работает быстрее, чем реализация с помощью бинариых пирамид.
Алгоритм Дейкстры имеет некоторую схожесть как с поиском в ширину (см. раздел 22.2), так и с алгоритмом Прима для построения минимальных остовных деревьев (см. раздел 23.2). Поиск в ширину он напоминает в том отношении, что множество Я соответствует множеству черных вершин, используемых при поиске в ширину; точно так же, как вершинам множества Е сопоставляются окончательные веса кратчайших путей, так и черным вершинам при поиске в ширину сопоставляются правильные расстояния. На алгоритм Прима алгоритм Дейкстры похож в том плане, что в обоих алгоритмах с помощью неубывающей очереди с приоритетами находится "легчайшая" вершина за пределами заданнс го множества (в алгоритме Дейкстры это множество Я, а в алгоритме Прима— Глава 24. Кратчайшие нута из одной вершины вырациваемое остовное дерево), затем эта вершина добавляется в множество, после чего соответствующим образом корректируются и упорядочиваются веса оставшихся за пределами множества вершин.
Упражнении 24.3.3 Выполните алгоритм Дейкстры над ориентированным графом, изображенным на рис. 24,2. Рассмотрите два варианта задачи, в одном из которых истоком является вершина я, а в другом — вершина ж Используя в качестве образца рис. 24.6, укажите, чему будут равны значения 4 и я и какие вершины будут входить в множество Я после каждой итерации цикла и Ые. г4.з.г Приведите простой пример ориентированного графа с отрицательными весами ребер, для которого алгоритм Дейкстры дает неправильные ответы. Почему доказательство теоремы 24.6 не годится, если веса ребер могут быть отрицательными? 24.3.3 Предположим, что мы изменяем строку 4 алгоритма Дейкстры следующим образом. 4 чиЫе (Я) > 1 В результате этого изменения цикл лчЫе выполняется ٠— 1 раз, а не )У) раз.
Корректен ли предложенный алгоритм? 24,3.4 Профессор написал программу, которая, как он утверждает, реализует алгоритм Дейкстры. Программа генерирует значения ш 4 и с. и для каждой вершины с е У. Приведите алгоритм со временем работы 0(У + Е), проверяющий выход программы профессора. Он должен определять, соответствуют ли атрибуты Н и я атрибутам некоторого дерева кратчайших путей. Вы можете считать, что веса всех ребер неотрицательны. 24.3.5 Профессор думает, что он разработал более простое доказательство корректности алгоритма Дейкстры.
Он утверждает, что алгоритм Дейкстры ослабляет ребра на каждом кратчайшем пути в графе в том порядке, в котором они находятся в пути, а следовательно, свойство ослабления пути применимо к каждой вершине, достижимой нз истока. Покажите, что профессор ошибается, построив ориентированный граф, для которого алгоритм Дейкстры ослабляет ребра кратчайшего пути не по порядку. 24.3.
б Пусть дан ориентированный граф С = (У, Е), с каждым ребром (и, с) е Е которого связано значение г(п, с), являющееся действительным числом в интерва- Часть ~'!. Алгораасмм длл работм с грифами 70г ле О < г(п, о) ( 1 и представляющее надежность соединительного кабеля между вершиной и и вершиной ю. Величина г(и, о) интерпретируется как вероятность того, что в канале, соединяющем вершины и и о, не произойдет сбой; при этом предполагается, что все вероятности независимы. Сформулируйте эффективный алгоритм, позволяющий найти наиболее надежный путь, соединяющий две заданные вершины. 24.3.7 Пусть С = (У, Е) — взвешенный ориентированный граф с положительной весовой функцией и: Š— ~ (1,2,..., И'), где И' — некоторое положительное целое число.
Будем считать, что ни для каких двух вершин кратчайшие пути, ведущие из истока в в зти вершины, не имеют одинаковых весов. Предположим, что определен невзвешенный ориентированный граф С' = (У 11 У',Е'), в котором каждое ребро (ц, о) е Е заменяется го(и, о) последовательными ребрами единичного веса. Сколько вершин содержит граф С'? Теперь предположим, что в графе С' выполняется поиск в ширину. Покажите, что порядок, в котором вершины множества У окрашиваются в черный цвет при поиске в ширину в графе С', совпадает с порядком извлечения вершин множества У из очереди с приоритетами при выполнении алгоритма Дейкстры над графом С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
