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