Часть 5. Алгоритмы на графах

Все наши алгоритмы поиска кратчайших путей до сих пор содержали одно из двух ограничений на задачу кратчайших путей, так чтобы с их помощью можно было получить эффективное решение: они либо запрещали циклы, либо запрещали отрицательные веса. Существуют ли менее строгие ограничения, которые можно было бы наложить на сети, содержащие как циклы, так и отрицательные веса, при которых мы все еще получали бы разрешимые задачи кратчайших путей? Мы затронули ответ на этот вопрос в начале гла­вы, когда нам требовалось добавить ограничение, состоящее в том, что пути должны быть настолько просты, чтобы задача имела бы смысл в случае наличия отрицательных циклов. Возможно, нам следует ограничить внимание к сетям, которые не имеют таких циклов?

Кратчайшие пути в сетях без отрицательных циклов. Для заданной сети, которая мо­жет содержать ребра с отрицательными весами, но не содержит циклов отрицательного веса, решим одну из следующих задач: найти кратчайший путь, соединяющий две задан­ных вершины (задача поиска кратчайшего пути), найти кратчайшие пути из заданной вер­шины во все другие вершины (задача с единственным источником), или найти кратчай­шие пути, соединяющие все пары вершин (задача всех пар).

Доказательство свойства 21.18 оставляет двери открытыми для эффективных алгорит­мов решения этой задачи, поскольку оно терпит неудачу, если запретить отрицательные циклы. Чтобы решить задачу поиска гамильтонова пути, необходимо иметь возможность решать задачи поиска кратчайших путей в сетях, которые содержат огромные количества отрицательных циклов.

Кроме того, много практических задач сводятся в точности к задаче нахождения крат­чайших путей в сетях, которые не содержат отрицательных циклов. Мы уже видели один такой пример.

Свойство 21.19. Задана календарного планирования работ с конечными сроками сводится к задаче поиска кратчайших путей в сетях, которые не содержат отрицательных циклов.

Доказательство: Аргументация, которую мы использовали при доказательстве свойства 21.15, показала, что построение в доказательстве свойства 21.16 ведет к сетям, не со­держащим отрицательных циклов. Из задачи календарного планирования работ мы создаем задачу разностных ограничений с переменными, которые соответствуют вре­менам начала работ, а из задачи разностных ограничений мы создаем сеть. Мы дела­ем отрицательными все веса, чтобы перейти от задачи поиска наиболее длинных пу­тей к задаче поиска кратчайших путей - преобразование, которое соответствует изменению знаков всех неравенств. Любой простой путь в сети из i в j соответствует последовательности неравенств, включающих переменные. Из существования такого пути, за счет сокращения этих неравенств, получается, что х_i — х_j- < w_ij, где w _ij есть сум­ма весов на пути из i в j Отрицательный цикл соответствует 0 в левой части этого не­равенства и отрицательному значению в правой части, так что существование такого цикла является противоречием. ■

Как мы отмечали, когда впервые обсуждали задачу календарного планирования работ в разделе 21.6, это утверждение безоговорочно предполагает, что наши задачи календар­ного планирования работ являются выполнимыми (т.е. имеют решение). На практике же мы не должны делать подобного допущения, и часть вычислительных затрат должна быть отведена на определение выполнимости задачи календарного планирования с конечны-

Глава 21. Кратчайшие пути

ми сроками. В построении доказательства свойства 21.19 отрицательный цикл в сети предполагает, что за­дача невыполнима, так что данная задача соответству­ет следующей.

Обнаружение отрицательных циклов. Содержит ли данная сеть отрицательный цикл? Если это так, то найти один такой цикл.

С одной стороны, эта задача не обязательно про­стая (простые алгоритмы проверки циклов для оргра­фов не применяются); с другой стороны, она не обя­зательно сложная (сведение из свойства 21.16 в отношении задачи поиска гамильтонова пути не при­меняется). Первое, что мы предпримем, так это раз­работаем алгоритм решения этой задачи.

В приложениях задач календарного планирования с конечными сроками отрицательные циклы соответ­ствуют состояниям ошибки, которые по-видимому редки, но наличие которых мы должны проверять. Мы могли бы даже разработать алгоритмы, которые удаляют ребра, чтобы разорвать отрицательный цикл, и повторяются до тех пор, пока существует хотя бы один такой цикл. В других приложениях обнаружение отрицательных циклов является основной целью, как в следующем примере.

Арбитражные операции (скупка и продажа ценных бумаг с целью получения выгоды). Многие газеты пе­чатают таблицы курсов обращения мировых валют (см., например, рис. 21.27). Мы можем рассматривать такие таблицы как матрицы смежности, представляю­щие полные сети. Ребро s-t с весом х означает, что мы можем конвертировать одну единицу валюты s в x единиц валюты t. Пути в сети задают многошаговые конверсии. Например, если существует также ребро t-w с весом у, то путь s-t-w представляет способ, по­зволяющий конвертировать одну единицу валюты s в ху единиц валюты w. Можно было бы ожидать, что ху будет равен весу s-w во всех случаях, однако рассмат­риваемые таблицы являются сложной динамичной си­стемой, где такая последовательность не может быть гарантирована. Если мы находим случай, где ху мень­ше, чем вес s-w, то мы в состоянии перехитрить сис­тему. Предположим, что вес w-s есть z и xyz > 1, тог-

РИС. 21.27. АРБИТРАЖНЫЕ ОПЕРАЦИИ

Таблица в верхней части задает переводные коэффициенты одной валюты в другую. Например, второй элемент в верхнем ряду говорит, что за $1 можно купить 1.631 единиц валюты Р. Конверсия $1000 в валюту Р и обратно должна дать $1000*(1.631)*(0.613) = $999, т.е. потеря составляет $1. Однако конверсия $1000 в валюту Р, затем в валюту Y u возврат обратно прино­сит прибыль

$Ю00*(1.631)*(0.411)*(1.495) = $1002, т.е. 0.2%. Если сделать отрицательным логарифм всех чисел в таблице (внизу), можно считать, что получена матрица смежности для полной сети с весами ребер, которые могут быть как положи­тельными, так и отрицательными. В этой сети узлы соответствуют валютам, ребра — конверсиям, а пути — последовательностям конверсии. Только что описанная конверсия соответствует циклу $-P-Y-$ в графе, причем вес это цикла составляет -0.489 + 0.800 -0.402 = -0.002. Лучшая возможность для совершения арбитражных операций соответствует наиболее короткому циклу в графе.

Часть 5. Алгоритмы на графах

ражных операций (arbitrage), которые позволили бы нам получать безграничные доходы, если бы не суще­ствовало сил, действующих вне пределов модели, та­ких, например, как ограничения на размер сделок. Чтобы преобразовать эту задачу в задачу кратчайших путей, мы логарифмируем все числа так, чтобы веса путей соответствовали сумме весов ребер вместо их умножения, а затем мы делаем их отрицательными, дабы обратить сравнение. Тогда веса ребер могли бы оказаться отрицательными или положительными, а кратчайший путь из s в t дал бы лучший способ кон­версии валюты s в валюту t. Цикл с наименьшим ве­сом указал бы лучшую возможность для арбитражных операций, однако интерес представляет любой отри­цательный цикл.

Можно ли обнаружить отрицательные циклы в сети или найти кратчайшие пути в сетях, которые не содержат отрицательных циклов? Существование эф­фективных алгоритмов для решения этих задач не противоречит NP-трудности общей задачи, которая была доказана в свойстве 21.18, поскольку сведение задачи поиска гамильтонова пути к произвольной за­даче не известно. В частности, сведение свойства 21.18 говорит о том, чего мы не можем сделать: перехит­рить алгоритм, который гарантирует, что можно эф­фективно найти путь с наименьшим весом в любой заданной сети, если в ней допускаются отрицательные веса ребер. Такая постановка задачи представляется слишком общей. Но мы можем решить ограниченные версии только что упомянутой задачи, хотя это и не так легко, как это имеет место для других ограниченных вер­сий данной задачи (положительные веса и ациклические сети), которыми мы занимались ранее в этой главе.

В общем случае, как отмечалось в разделе 21.2, ал­горитм Дейкстры не работает при наличии отрица­тельных весов, даже когда мы ограничиваемся рассмотрением сетей, которые не содержат отрица­тельных циклов. Рисунок 21.28 иллюстрирует это ут­верждение. Основное затруднение состоит в том, что в этом алгоритме пути рассматривают­ся в порядке возрастания их длины. Доказательство правильности алгоритма (см. свойство 21.2) предполагает, что добавление ребра к пути делает этот путь более длинным.

Алгоритм Флойда не делает такого допущения и эффективен даже тогда, когда веса ребер могут быть отрицательными. Если нет отрицательных циклов, он вычисляет крат­чайшие пути; замечателен тот факт, что в случае существования отрицательных циклов, этот алгоритм обнаруживает, по крайней мере, один из них.

Глава 21, Кратчайшие пути

Свойство 21.20. Алгоритм Флойда решает задачу обнаружения отрицательного цикла и задачу поиска кратчайших путей для всех пар в сетях, которые не содержат отрицатель­ных циклов, за время, пропорциональное V³.

Доказательство: Доказательство свойства 21.8 не зависит от того, будут ли веса ребер отрицательными, тем не менее, нам нужно интерпретировать результаты по-иному, когда присутствуют ребра с отрицательными весами. Каждый элемент в матрице сви­детельствует о том, что алгоритм обнаружил путь этой длины. В частности, любой от­рицательный элемент на диагонали матрицы расстояний суть свидетельство наличия, по крайней мере, одного отрицательного цикла. При наличии отрицательных циклов мы не можем непосредственно делать какие-либо дальнейшие выводы, поскольку пути, которые алгоритм неявно проверяет, не обязательно просты, поскольку они могут содержать один и более обходов по одному и более отрицательных циклов. Од­нако, если отрицательных циклов нет, то пути, которые вычисляются алгоритмом, просты, поскольку для любого пути с циклом можно предположить существование такого пути, который соединяет те же две точки, но который содержит меньше ре­бер и не обладает более высоким весом (тот же путь с удаленным циклом). ■

Доказательство свойства 21.20 не дает конкретной информацию о том, как найти кон­кретный отрицательный цикл из матриц расстояний и путей, вычисляемых по алгоритму Флойда. Мы оставляем это задание читателям на самостоятельную проработку (см. упраж­нение 21.122).

Алгоритм Флойда решает задачу поиска кратчайших путей для всех пар в графах, ко­торые не содержат отрицательных циклов. Учитывая неудачу алгоритма Дейкстры в се­тях, которые, возможно, содержат отрицательные веса, мы могли бы воспользоваться алгоритмом Флойда для решения задачи для всех пар в разреженных сетях, не содержа­щих отрицательных циклов, за время, пропорциональное V³. Если мы имеем задачу с одним источником в таких сетях, можно применить это V³-решение задачи для всех пар. И хотя это сродни пальбе из пушки по воробьям, но все же лучше того, что мы наблю­дали для задачи с одним источником. Можем ли мы разработать более быстрые алгорит­мы для этих задач - такие, время выполнения которых сравнимо с алгоритмом Дейкст­ры, когда веса ребер положительны (Е lgV для кратчайших путей из единственного источника и VE lg V для кратчайших путей всех пар)? На этот вопрос можно ответить ут­вердительно в отношении задачи всех пар, кроме того, есть возможность снизить сто­имость худшего случая до V Е для задачи с единственным источником. А вот вопрос пре­одоления барьера VE для общей задачи поиска кратчайших путей с единственным источником является по-прежнему открытым.

Следующий подход, развитый Р. Беллманом (R. Bellman) и Л. Фордом (L. Ford) в кон­це пятидесятых годов, предоставляет простую и эффективную основу для начала решения задач поиска кратчайших путей с единственным источником в сетях, не содержащих от­рицательных циклов. Чтобы вычислить кратчайшие пути из вершины s, мы поддержива­ем (как обычно) индексированный вершинами вектор wt, такой, что wt [t] содержит дли­ну кратчайшего пути из s в t. Мы инициализируем wt [s] значениями 0, а все другие элементы wt — большим сигнальным значением, после чего вычисляем кратчайшие пути, как показано ниже:

Просматривая ребра сети в любом порядке, произвести ослабление вдоль каждого ребра. Выполнить V таких действий.

Часть 5. Алгоритмы на графах

Эта последовательность показывает построение матриц всех кратчайших путей для орграфа с отрицательными весами по алгоритму Флойда. Первый шаг является таким же, как показанный на рис. 21.14. На втором шаге в игру вступает отрицательное ребро 5-1 и вскрываются пути 5-1-2 и 5-1-4. Алгоритм включает точно ту же последовательность шагов ослабления для любых весов ребра, однако результаты отличаются.