Алгоритмы - построение и анализ (1021735), страница 150
Текст из файла (страница 150)
б) Покажите, как в течение времени 0 (Е) вычислить кратчайшие пути из единого истока в е-плотном ориентированном графе С = (У, Е), в котором отсутствуют ребра с отрицательным весом. (Указание: выберите величину И как функцию е.) в) Покажите, как в течение времени О(УЕ) решить задачу поиска кратчайших путей между всеми парами вершин в е-плотиом ориентированном графе С = (У, Е), в котором отсутствуют ребра с отрицательным весом.
г) Покажите, как в течение времени 0(УЕ) решить задачу поиска кратчайших путей между всеми парами вершин в е-плотном ориентированном графе С = (У, Е), в котором допускается наличие ребер с отрицательным весом, но отсутствуют циклы с отрицательным весом. Заключительные замечания Неплохое обсуждение задачи о поиске кратчайших путей между всеми парами вершин содержится в книге Лоулера (Ьачг1ег) [19б], хотя в ней и не анализируются решения для разреженных графов.
Алгоритм перемножения матриц он считает Глава 25. Кратчайшие пути между всеми парами вершин 733 результатом народного творчества. Алгоритм Флойда-Варшалла был предложен Флойдом (Е)суд) [89] и основывался на теореме Варшалла (1УагзЬа11) [308], в которой описывается, как найти транзитивное замыкание булевых матриц. Алгоритм Джонсона ()оЬпзоп) взят из статьи [1б8]. Несколько исследователей предложили улучшенные алгоритмы, предназначенные для поиска кратчайших путей с помощью умножения матриц. Фридман (Ргейпап) [95] показал, что задачу о поиске кратчайшего пути между всеми парами вершин можно решить, выполнив 0 (1'з~з) операций по сравнению суммарных весов ребер; в результате получится алгоритм, время работы которого равно 0 [1 "з (1818 'г'/18]Г)~~~), что несколько лучше соответствующей величины для алгоритма Флойда-Варшалла.
Еще одно направление исследований показывает, что к задаче о поиске кратчайших путей между всеми парами вершин можно применить алгоритмы быстрого умножения матриц (см. заключительные замечания к главе 28). Пусть 0 (и ) — время работы самого производительного алгоритма, предназначенного для перемножения матриц размером и х и; в настоящее время ш < 2.376 [70]. Галил (ОаИ) и Маргалит (Магйарп) [105, 106], а также Зайдель (ЗеЫе1) [270] разработали алгоритмы, решающие задачу о поиске кратчайших путей между всеми парами вершин в неориентированных невзвешенных графах в течение времени 0 (1' р (1')), где р (и) — функция, полилогарифмически ограниченная по п.
В плотных графах время работы этих алгоритмов меньше величины О (1' Е), необходимой для Щ поисков в ширину. Некоторые исследователи расширили эти результаты и разработали алгоритмы, предназначенные для поиска кратчайших путей между всеми парами вершин в неориентированных графах с целочисленными весами ребер в диапазоне [1,2,..., И'). Среди таких алгоритмов быстрее всего в асимптотическом пределе ведет себя алгоритм Шошана (Броз)зап) и Цвика (Яичек) [278], время работы которого равно 0 (И" Ъ' р (1' И')).
Каргер (Кагйег), Коллер (Ко!1ег) и Филлипс (РЫ!11рз) [170], а также независимо Мак-Геч (МсОеосЬ) [215] дали временную границу, зависящую от Е",— подмножества ребер из множества Е, входящих в некоторый кратчайший путь. Для заданного графа с неотрицательными весами ребер эти алгоритмы завершают свою работу за время О (1' Е*+ Уз 18 Ъ). Это лучший показатель, чем ~1",- кратное выполнение алгоритма Дейкстры, если ~Е*~ = о (Е). Ахо (АЬо), Хопкрофт (Норсгой) и Ульман (1Л)тап) [5] дали определение алгебраичесюй структуры, известной как "замкнутое полуюльцо".
Эта структура служит общим каркасом для решения задач о поиске путей в ориентированных графах. Алгоритм Флойда-Варшалла и описанный в разделе 25.2 алгоритм транзитивного замыкания — примеры алгоритмов поиска путей между всеми парами вершин, основанных на замкнутых полукольцах. Маггс (Маййв) и Плоткин (Р1обс(п) [208] показали, как искать минимальные остовные деревья с помощью замкнутых полуколец. ГЛАВА 26 Задача о максимальном потоке Так же, как дорожную карту можно смоделировать ориентированным графом, чтобы найти кратчайший путь из одной точки в другую, ориентированный граф можно интерпретировать как некоторую транспортную сеть и использовать его для решения задач о потоках вещества в системе трубопроводов. Представим, что некоторый продукт передается по системе от источника, где данный продукт производится, к стоку, где он потребляется. Источник производит продукт с некоторой постоянной скоростью, а сток с той же скоростью потребляет продукт.
Интуитивно потоком продукта в любой точке системы является скорость движения продукта. С помощью транспортных сетей можно моделировать течение жидкостей по трубопроводам, движение деталей на сборочных линиях, передачу тока по электрическим сетям, информации — по информационным сетям и т.д. Каждое ориентированное ребро сети можно рассматривать как канал, по которому движется продукт. Каждый канал имеет заданную пропускную способность, которая характеризует максимальную скорость перемещения продукта по каналу, например, 200 литров жидкости в минуту для трубопровода или 20 ампер для провода электрической цепи. Вершины являются точками пересечения каналов; через вершины, отличные от источника и стока, продукт проходит, не накапливаясь.
Иными словами, скорость поступления продукта в вершину должна быть равна скорости его удаления из вершины. Это свойство называется свойством сохранения потока; в случае передачи тока по электрическим цепям ему соответствует закон Кирхгофа. В задаче о максимальном потоке мы хотим найти максимальную скорость пересылки продукта от источника к стоку, при которой не будут нарушаться ограничения пропускной способности. Это одна из простейших задач, возникающих Глава 26. Задача о максимальном потоке 735 в транспортных сетях, и, как будет показано в данной главе, существуют эффективные алгоритмы ее решения. Более того, основные методы, используемые в алгоритмах решения задач о максимальном потоке, можно применять для решения других задач, связанных с транспортными сетями. В данной главе предлагается два общих метода решения задачи о максимальном потоке.
В разделе 26.1 формализуются понятия транспортных сетей и потоков, а также дается формальное определение задачи о максимальном потоке. В разделе 26.2 описывается классический метод Форда-Фалкерсона (Рогд апд Ри1кегзол) для поиска максимального потока. В качестве приложения данного метода в разделе 26.3 осуществляется поиск максимального паросочетания в неориентированном двудольном графе. В разделе 26.4 описывается метод "проталкивания предпотока" ("рцзЬ-ге!аЬе1"), который лежит в основе многих наиболее быстрых алгоритмов для задач в транспортных сетях.
В разделе 26.5 рассматривается еще один алгоритм, время работы которого составляет О (1'з). Хотя он и не является самым быстрым известным алгоритмом, зато позволяет проиллюстрировать некоторые методы, используемые в асимптотически более быстрых алгоритмах, и на практике является достаточно эффективным. 26.1 Транспортные сети В данном разделе мы дадим определение транспортных сетей в терминах теории графов, обсудим их свойства, дадим точное определение задачи о максимальном потоке, а также введем некие полезные обозначения. Транспортные сети и потоки Транспортная сеть (бои пепчогк) С = (КЕ) представляет собой ориентированный граф, в котором каждое ребро (и, и) е Е имеет неотрицательную пропускнуго способность (сарасйу) с(и,и) > О.
Если (и,и) ф Е, предполагается, что с (и, и) = О. В транспортной сети выделяются две вершины: источник (зощсе) а и сток (гйп1с) 1. Для удобства предполагается, что каждая вершина лежит на неком пути из источника к стоку, т.е. для любой вершины и е У существует путь в - и - 1. Таким образом, граф является связным и 1Е! > 1Ц вЂ” 1.
На рис. 26.1а показан пример транспортной сети С = (К Е) для задачи грузовых перевозок компании 1лску РисЕ Источник в — это фабрика в Ванкувере, а сток г — склад в Виннипеге. Шайбы доставляются через промежуточные города, но за день из города и в город и можно отправить только с(и, и) ящиков. На рисунке приведена пропускная способность каждого ребра сети. На рис. 26.16 показаны потоки в транспортной сети. Поток У в сети С имеет значение 1г"1 = 19.
Показаны только положительные потоки. Если г" (и, и) > О, то ребро (и, и) снабжено меткой )'(и, и)/с (и, и) (косая черта используется только для того, чтобы отделить Часть Ч1. Алгоритмы для работы с графами 736 )езсссзс С~скатю /г -,У ~ ~яу~ Хыгарс Рс1,сч а) б) Рис. 26Д. Пример транспортной сети и сс потоки поток от пропускной способности и не обозначает деление). Если Г' (и, и) < О, то у ребра (и, и) показана толью его пропускная способность. Теперь дадим формальное определение потоков. Пусть С = (Ч; Е) — транспортная сеть с функцией пропускной способности с. Пусть з — источник, а г— сток.
Потокам (йож) в С является действительная функция Г: У х У -+ В„ удовлетворяющая следующим трем условиям. Ограничение пропускной способности (сарасйу сопзпашг): у (и,и) < с(и,с) для всех и, и Е У. Антисимметричночть (зкесг зупипену): Г' (и, о) = — Г' (и, и) для всех и, и Е У. Сохранение потока (йод сопзегчапоп): для всех и е У вЂ” (з, г) ~~) г(и,и) =О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
