Алгоритмы - построение и анализ (1021735), страница 145
Текст из файла (страница 145)
Кратчайшие пути из одной вершины 707 (Роп1) [93]. Беллман описывает, какое отношение имеют кратчайшие пути к разностным ограничениям. Лоулер (?.ач!ег) [196] описывает алгоритм с линейным временем работы для поиска кратчайших путей в ориентированном ациклическом графе, который он рассматривает как часть "народного творчества". Если вес каждого из ребер выражается сравнительно малыми неотрицательными целыми числами, задача о кратчайших путях из одной вершины решается с помощью более эффективных алгоритмов. Последовательность значений, возвращаемых в результате вызовов процедуры Ехтклст М1и в алгоритме Дейкстры, монотонно возрастает со временем.
Как говорилось в заключительных замечаниях к главе 6, в этом случае существует несколько структур данных, позволяющих эффективнее реализовать различные операции над очередями с приоритетами, чем бинарная пирамида или пирамида Фибоначчи. Ахуя (АЬп]а), Мельхорн (МеЬ)Ьотп), Орлин (Ог1ш) и Таржан (Тат]ап) [8] предложили для графов с неотрицательными весами ребер алгоритм со временем работы 0 (Е+ Ъ'~(ТдУ), где И' — максимальный вес ребра графа. Наилучшие границы достигнуты Торупом (ТЬогир) [299], который предложил алгоритм со временем работы 0(Е1818Ъ'), и Раманом (йшпап) [256], чей алгоритм имеет время работы 0(Е + Ъ' пйп((18 Ъ')1/з+', (18 И')1~4+')). Оба алгоритма используют объем памяти, зависящий от размера слова машины, на которой выполняется алгоритм.
Хотя объем использующейся памяти может оказаться неограниченным в зависимости от размера входных данных, с помощью рандомизированного хеширования его можно снизить до линейно зависящего от размера входных данных. Для неориентированных графов с целочисленными весами Торуп [298] привел алгоритм со временем работы 0 (Ъ'+ Е), предназначенный для поиска кратчайших путей из одной вершины. В отличие от алгоритмов, упомянутых в предыдущем абзаце, этот алгоритм — не реализация алгоритма Дейкстры, поскольку последовательность значений, возвращаемых вызовами процедуры Ехтнлст Мпч, не является монотонно неубывающей.
Для графов, содержащих ребра с отрицательными весами, алгоритм, предложенный Габовым (ОаЬо~ч) и Таржаном [104], имеет время работы 0(тЯЕ18(Ъ'Ъ7)), а предложенный Гольдбергом (Оо1дЬегй) [118] выполняется в течение времени 0 (~ТЕ 18 И~), где И' = шах(ь 4 ел ([тс (" с) О.
Черкасский (СЬегкаазку), Гольдберг (Оо!дЬегй) и Радзик (йа<Ы1с) [57] провели большое количество экспериментов по сравнению различных алгоритмов, предназначенных для поиска кратчайших путей. ГЛАВА 25 Кратчайшие пути между всеми парами вершин В этой главе рассматривается задача о поиске кратчайших путей между всеми парами вершин графа. Эта задача может возникнуть, например, при составлении таблицы расстояний между всеми парами городов, нанесенных на атлас дорог. Как и в главе 24, в этой задаче задается взвешенный ориентированный граф С = = (КЕ) с весовой функцией ш: Е -> 8., отображающей ребра на их веса, выраженные действительными числами.
Для каждой пары вершин и, е б 1' требуется найти кратчайший (обладающий наименьшим весом) путь из вершины и в вершину е, вес которого определяется как сумма весов входящих в него ребер. Обычно выходные данные представляются в табличной форме: на пересечении строки с индексом и и столбца с индексом о расположен вес кратчайшего пути из вершины и в вершину и.
Задачу о поиске кратчайших путей между всеми парами вершин можно решить, ~Ъ'~ раз запустив алгоритм поиска кратчайших путей из единого истока, каждый раз выбирая в качестве истока новую вершину графа. Если веса всех ребер неотрицательные, можно воспользоваться алгоритмом Дейкстры.
Если используется реализация неубывающей очереди с приоритетами в виде линейного массива, то время работы такого алгоритма равно О (1~з + УЕ) = О (1'з). Если же неубывающая очередь с приоритетами реализована в виде бинарной неубывающей пирамиды, то время работы будет равно О (~' Е 1к У), что предпочтительнее для разреженных графов. Можно также реализовать неубывающую очередь с приоритетами как пирамиду Фибоначчи; в этом случае время работы алгоритма равно О (1'"з 1к Ъ' + УЕ). Глава 25.
Кратчайшие пути между всеми парами вершин 709 Если допускается наличие ребер с отрицательным весом, алгоритм Дейкстры неприменим. Вместо него для каждой вершины следует выполнить алгоритм Беллмана-Форда, который работает медленнее. Полученное в результате время работы будет равно 0 (1гзЕ), которое на плотных графах можно записать как О (И4). В этой главе станет понятно, как лучше поступить. Будет также исследована связь задачи о кратчайших расстояниях между всеми парами вершин с умножением матриц, и изучена алгебраическая структура этой задачи. В отличие от алгоритмов поиска кратчайшего пути из фиксированного истока, в которых предполагается, что представление графа имеет вид списка смежных вершин, в большей части представленных в этой главе алгоритмов используется представление в виде матрицы смежности.
(В алгоритме Джонсона (1оЬпзоп) для разреженных графов используются списки смежных вершин.) Для удобства предполагается, что вершины пронумерованы как 1,2,..., ~Ц, поэтому в роли входных данных выступает матрица Иг размером и х и, представляющая веса ребер ориентированного графа С = (г', Е) с п вершинами. Другими словами, Иг = (ш,"), где 0 если г = 7, вес ориентированного ребра (г,7') если г ~ 2 и (г,7) е Е, (25.1) 00 если г ф 2 и (г,7') ф Е. Наличие ребер с отрицательным весом допускается, но пока что предполагается, что входной граф не содержит циклов с отрицательным весом.
Выходные данные представленных в этой главе алгоритмов„предназначенных для поиска кратчайших путей между всеми парами вершин, имеют вид матрицы П = (г(г ) размером п х и, где элемент г(г содержит вес кратчайшего пути из вершины г в вершину ~. Другими словами, если обозначить через б(г', з') кратчайший путь из вершины г в вершину з' (как это было сделано в главе 24), то по завершении алгоритма г(г = б (г, з'). Чтобы решить задачу о поиске кратчайших путей между всеми парами вершин со входной матрицей смежности, необходимо вычислить не только вес какдого из кратчайших путей, но также и матрицу яредглествования (ргебесеааог шаптх) П = (я;"), где величина я;" имеет значение мп., если г = у или путь из вершины г' в вершину 7' отсутствует; в противном случае х; — предшественник вершины г' на некотором кратчайшем пути из вершины г.
Точно так же, как описанный в главе 24 подграф предшествования С„является деревом кратчайших путей для заданного истока, подграф, индуцированный г-й строкой матрицы П, должен бьгть деревом кратчайших путей с корнем г'. Определим для каждой вершины г Е 1~ лодграф лредшествовалил (ргебесеззог зпЬягарЬ) графа С для вершины г как граф С„,; = (К,,;, Е„,;), где Часть Ч1. Алгоритмы для работы с графами 710 Е; = ((яд,3): 3 е К,; — (г)) . Если С„; — дерево кратчайших путей, то приведенная ниже процедура, представляющая собой модифицированную версию описанной в главе 22 процедуры Ркп4т Рлтн, выводит кратчайший путь из вершины 1 в вершину 32 Ршнт Аы. Рл|кз Бноктцзт Рлтн(П,1,3) 1 1г" 1= 3 2 1пеп рпп! 1 3 е!ае Ыя;, =ни.
4 1пеп рпш "Не существует пути из" 1 "в"' 5 5 еие Ркпчт Аы. Рыка Бноктпзт Рлтн(П,г,я;,) б рппг з' Чтобы подчеркнуть важные особенности представленных в этой главе алгоритмов поиска кратчайших путей между всеми парами вершин, создание матриц предшествования и их свойств не будет рассматриваться здесь так же подробно, как это было в главе 24 в случае подграфа предшествования. Основные моменты предлагается рассмотреть в некоторых упражнениях.
Краткое содержание главы В разделе 25.1 представлен алгоритм динамичесюго программирования, основанный на операции умножения матриц, юторый позволяет решить задачу о поиске кратчайших путей между всеми парами вершин. С помощью метода "многократного возведения в квадрат" можно сделать так, чтобы время работы этого алгоритма было равно 9 (Уз 1я У). В разделе 25.2 приведен другой алгоритм динамичесюго программирования — алгоритм Флойда-Варшалла (Р)оуо-%агзпаП). Время работы этого алгоритма равно О (Уз). В этом же разделе исследуется задача поиска транзитивного замыкания ориентированного графа, связанная с задачей о поиске кратчайших путей между всеми парами вершин.
Наконец, в разделе 25.3 представлен алгоритм Джонсона. В отличие от других алгоритмов, описанных в этой главе, в алгоритме Джонсона применяется представление графа в виде списка смежных вершин. Этот алгоритм позволяет решить задачу о поиске кратчайших путей между всеми парами вершин за время О (Уз 1я У + 'УЕ), что делает его пригодным для больших разрешенных графов. Перед тем как продолжить, нужно принять некоторые соглашения для представлений в виде матрицы смежности.
Во-первых, в общем случае предполагается, что входной граф С = (У, Е) содержит и вершин, так что и = Щ. Вовторых, будет использоваться соглашение об обозначении матриц прописными буквами, например, 1У, Ь или 23, а их отдельных элементов — строчными буквами с нижними индексами, например, ю;, 1г или сг .
Возле некоторых матриц Глава 25. Кратчайшие пути между всеми парами вершин 711 будут взятые в скобки верхние индексы, указывающие на количество итераций, например, Ь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}
