Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 149
Текст из файла (страница 149)
Габов (ОаЬота), Галил (бай!), Спенсер (Брепсег) и Таржан [119] усовершенствовали этот алгоритм, доведя время его работы до 0(Есг(Е, К)). Чазел (СЬахе!1е) [59] разработал алгоритм со временем работы 0(Е сг(Е, К)), где о(Е, )7) — функция, обратная функции Аккермана (см. главу 21). В отличие от перечисленных ранее, алгоритм Чазела не является жадным.
С задачей поиска минимального остовного дерева связана задача проверки освьовного дерева (зрапшпй !гее чепьйсаг1оп), в которой для данного графа С = Глаеа 23. Мииииальиые остовиые деревьв 619 (!1 Е) и дерева Т С Е требуется определить, является ли Т минимальным остовным деревом С. Кинг (Кшй) [202] разработал алгоритм решения данной задачи за линейное время, основанный на работах Комлеса (Кош)оз) [214] и Диксона (О!хоп), Рауха (йапсЬ) и Таржана [89]. Все описанные выше алгоритмы — детерминированные и относятся к модели на основе сравнений, описанной в главе 8. Картер (Кагйег), Клейн (К1е!и) и Таржан [194] разработали рандомизированный алгоритм поиска минимальных остовных деревьев, математическое ожидание времени работы которого составляет 0(11 + Е). Этот алгоритм использует рекурсию наподобие алгоритма с линейным временем работы из раздела 9.3: рекурсивный вызов для вспомогательной задачи определяет подмножество ребер Е', которое не может находиться ни в одном минимальном остовном дереве.
Другой рекурсивный вызов, работаюший с подмножеством Š— Е', строит минимальное остовное дерево. Алгоритм также использует идеи из алгоритмов Борувки и Кинга. Фредман и Виллард (%!11агб) [115] показали, как найти минимальное остовное дерево за время 0($'+ Е) с использованием детерминированного алгоритма, не основанного на сравнениях. Их алгоритм предполагает, что данные представляют собой Ь.битовые целые числа и что память компьютера состоит из адресуемых б-битовых слов. Глава 24. Кратчайшие пути из одной вершины Водителю автомобиля нужно найти самый короткий путь из Киева в Запорожье. Допустим, у него есть карта Украины, на которой указаны расстояния между каждой парой пересечений дорог. Как найти кратчайший маршрут? Один из возможных способов — пронумеровать все маршруты из Киева в Запорожье, просуммировать длины участков на каждом маршруте и выбрать кратчайший из них. Однако легко понять, что даже если исключить маршруты, содержащие циклы, получится очень много вариантов, большинство которых просто не имеет смысла рассматривать.
Например, очевидно, что маршрут из Киева в Запорожье через Львов — далеко не лучший выбор. Точнее говоря, такой маршрут никуда не годится, потому что Львов находится относительно Киева совсем в другой стороне. В этой главе и в главе 25 будет показано, как эффективно решаются такие задачи. В задаче а кратчайшем пути (з!гопезг-раг)гз ргоЫеш) задается взвешенный ориентированный граф С = (Ъ; Е) с весовой функцией ю; Š— ~ В, отображающей ребра на их веса, значения которых выражаются действительными числами. Вес (чге1йпг) пути р = (со, сг,..., сь) равен суммарному весу входящих в него ребер; ю(р) = ~~' ю( ч-ы ') Вес кратчайшего пути (аЬопезг-рагй ие1й)гг) б(и, и) из вершины и в вершину с определяется соотношением п пп(ю(р): и о), если существует путь из и в с, б(и,с) = оо в противном случае .
Тогда по определению кратчайший путь (зЬопезг райг) из вершины и в вершину и — это любой путь, вес которого удовлетворяет соотношению ю(р) = б(и, о). В примере, в котором рассматривается маршрут из Киева в Запорожье, карту дорог можно смоделировать в виде графа, вершины которого представляют перекрестки дорог, а ребра — отрезки дорог между перекрестками, причем вес каждого ребра равен расстоянию между соответствующими перекрестками. Цель— найти кратчайший путь от заданного перекрестка в Киеве (например, между ули- ВВ! Глава 2К Кратчайшие нута из одной вершины цами Клавдиевской и Корсуньской) к заданному перекрестку в Запорожье (скажем, между улицами Панфиловцев и Патриотической).
Вес каждого из ребер можно интерпретировать не как расстояние, а как другую метрику. Часто они используются для представления временных интервалов, стоимости, штрафов, убытков или любой другой величины, которая линейно накапливается по мере продвижения вдоль ребер графа и которую нужно свести к минимуму. Алгоритм поиска в ширину, описанный в разделе 22.2, представляет собой алгоритм поиска кратчайшего пути в неазвешенном графе, т.е.
в графе, каждому ребру которого приписывается единичный вес. Поскольку многие концепции, применяемые в алгоритме поиска в ширину, возникают при исследовании задачи о кратчайшем пути по взвешенным графам, рекомендуется перед дальнейшим чтением освежить в памяти материал раздела 22.2. Варианты Настоящая глава посвящена задаче а кратчайших иугаих из одной вершины (япй!е-зошсе аЬонезбраГ(зз ргойеш), в которой для заданного графа С = (1', Е) требуется найти кратчайшие пути, которые начинаются в определенной исходной вершине (зопгсе чепех) в е К (для краткости будем именовать ее истоком) и заканчиваются в каждой из вершин и е К.
Предназначенный для решения этой задачи алгоритм позволяет решать многие другие задачи, в том числе перечисленные ниже. Задача о кратчайших путях в одну вершину. Требуется найти кратчайшие пути в заданную целевую веривииу (Йеябпайоп чег$ех) 1, которые начинаются в каждой из вершин о. Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине. Задача о кратчайшем пути между заданной парой вершин. Требуется найти кратчайший путь из заданной вершины и в заданную вершину и.
Если решена задача поиска кратчайших путей из заданной исходной вершины о, то эта задача также решается. Более того, все известные для решения данной задачи алгоритмы имеют то же время работы в наихудшем случае, что и наилучшие алгоритмы поиска кратчайших путей из одной вершины. Задача о кратчайшем пути между всеми вершинами. Требуется найти кратчайший путь из каждой вершины и в каждую вершину е. Эту задачу также можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее. Кроме того, структура этой задачи представляет интерес сама по себе.
В главе 25 задача обо всех парах вершин исследуется более подробно. Оптимальная подструктура кратчайших путей Алгоритмы поиска кратчайших путей обычно основаны на том свойстве, что кратчайший путь между двумя вершинами содержит в себе другие кратчайшие пути. (В основе описанного в главе 26 алгоритма Эдмондов-Карпа (Едзпопдя- Часозо РЬ Алгоритмы длв работы с графами бв2 Катр), предназначенного для поиска максимального потока, также лежит это свойство.) Вспомним, что свойство оптимальной подструктуры — один из ключевых индикаторов применимости и динамического программирования (глава 15), и жадного метода (глава 16). Алгоритм Дейкстры (Р11квпа), с которым мы ознакомимся в разделе 24.3, представляет собой жадный алгоритм, а алгоритм Флойда— Уоршелла (Р(оуб — %агвЬаП), предназначенный для поиска кратчайшего пути между всеми парами вершин (см. раздел 25.2), — алгоритм динамического программирования.
В сформулированной ниже лемме данное свойство оптимальной структуры определяется более точно. Лемма 24.1 <Подлутл кратчайших лушей есть кратчайшие аута) Пусть р = (ио, ип ..., иь) — кратчайший путь из вершины ио в вершину гь в заданном взвешенном ориентированном графе С = ($; Е) с весовой функцией ш: Š— > К и пусть для любых 1 и 2', таких, что 0 < 1 < 2 < Ь, путь р;. = (и„и;+ы ..., Рэ) является подпутем р из вершины и, в вершину и . Тогда рп является кратчайшим путем из и, в и . Доказательства. Если разложить путь р на составные части ио ~ и, + и; РО Р*з Рзг иы то будет выполняться соотношение и (р) = ш(ро,) + из(рц) + ш(р ь).
Теперь предположим, что сушествует путь р', из вершины и, в вершину и; с вез РО 1 3 Рзг сом ш(р„) < ш(р;,). Тогда ио 1 и, -. и иь представляет собой путь из ио в иы вес которого из(ро,) + ш(рц) + из(р ь) меньше, чем ш(р), что противоречит предположению о том, что р является кратчайшим путем из вершины ио в вершину иь.
Ребра с отрицательным весом В некоторых экземплярах задачи о кратчайшем пути из фиксированного истока веса ребер могут принимать отрицательные значения. Если граф С = (Ъ; Е) не содержит циклов с отрицательным весом, достижимых из истока в, то вес кратчайшего пути б(в, и) остается вполне определенной величиной для каждой вершины и е 1', даже если он принимает отрицательное значение. Если же такой цикл достижим из истока в, веса кратчайших путей перестают быть вполне определенными величинами. В этой ситуации ни один путь из истока в в любую из вершин цикла не может быть кратчайшим, потому что всегда можно найти путь с меньшим весом, который проходит по предложенному "кратчайшему" пути, а затем обходит цикл с отрицательным весом.
Если на некотором пути из вершины в к вершине и встречается цикл с отрицательным весом, мы определяем б(в,и) = — оо. На рис. 24.1 проиллюстрировано влияние наличия отрицательных весов и циклов с отрицательным весом иа веса кратчайших путей. Поскольку из вершины в в вершину а ведет всего один путь (путь (в, а)), то выполняется равенство б(в, а) = ш(в, а) = 3. Аналогично имеется всего один путь из вершины в в вершину Ь, поэтому б(в, Ь) = ш(в, а) + ш(а, Ь) = 3 + ( — 4) = — 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
