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