Отрицательные циклы во взвешенных орграфах

Постановка задачи

Пусть G = (V, E) – ориентированный граф (орграф), имеющий m ребер и n вершин, ребра которого ассоциированы с вещественной стоимостной функцией wt: E ! R. Стоимость, wt(P), пути P в графе G равна сумме стоимостей ребер, входящих в P. Простой путь C, начальная и конечная вершины которого совпадают, называется циклом. Если wt(C) < 0, то C называется отрицательным циклом. Необходимо определить, существует ли подобный цикл в данном орграфе G с ребрами вещественной стоимости, и если существует – вывести этот цикл.

Задача нахождения отрицательного цикла тесно связана с задачей нахождения кратчайшего пути. В последней необходимо найти путь с минимальной стоимостью между двумя вершинами s и t. Легко увидеть, что кратчайший путь s-t существует в том и только том случае, если ни один путь s-t в графе G не содержит отрицательного цикла [1 , 13]. Также известно, что все кратчайшие пути от заданной вершины s до всех других вершин формируют дерево, называемое деревом кратчайших путей [1, 13].

Основные результаты

В случае орграфов общего вида лучшим алгоритмом для решения задачи нахождения отрицательного цикла (или вычисления дерева кратчайших путей в случае, если такого цикла не существует) является классический алгоритм Беллмана-Форда с временем исполнения O(nm) (см, например, [1]). Другие алгоритмы с той же временной сложностью приводятся в [4, 7, 12, 13]. Кроме того, в [11, глава 7] описано расширение алгоритма Беллмана-Форда, которое помимо обнаружения существующих отрицательных циклов и вывода их (при наличии) строит дерево кратчайших путей с корнем в некоторой вершине s, достигающих такие вершины u, у которых кратчайшие пути s-u не содержат отрицательного цикла. Для случая, когда стоимости дуг являются целыми числами не менее - L (L > 2), в [6] предложен более оптимальный алгоритм, исполняющийся за время O(mpn log L) и основанный на битовом масштабировании. Простой детерминированный алгоритм с ожидаемым временем исполнения O(n2 log n) с высокой вероятностью был приведен в [10]; он предназначен для широкого класса распределений входных данных, у которых стоимости ребер выбираются случайным образом в соответствии с независимой от конечных точек моделью (эта модель включает общий случай, при котором все стоимости ребер выбираются независимым образом из одного и того же распределения).

Лучшие результаты были получены для нескольких важных классов разреженных орграфов (т.е.е орграфов, имеющих m = O(n) ребер) – таких как планарные и внешнепланарные орграфы, орграфы малого рода и малой древесной ширины.

Для разреженных орграфов общего вида в [8] был предложен алгоритм для решения задачи нахождения отрицательного цикла за время O(n + y1'5 log y), где у – топологическая мера входного разреженного орграфа G, значение которой меняется от 1 до 0{n). Неформально у представляет минимальное количество внешнепланарных подграфов, удовлетворяющих определенным свойствам отделимости и полученных в результате декомпозиции графа G. В частности, у пропорционально y(G) + q, где G предполагается вложенным в ориентируемую поверхность рода y(G) таким образом, чтобы минимизировать количество q граней, совместно покрывающих все вершины. Например, если граф G является внешнепланарным, то у = 1, в результате для такого случая получаем оптимальный алгоритм с временем исполнения O(n). Алгоритм в [ ] не требует необходимого наличия такого вложения входного графа. В той же статье показано, что случайные графы Gn;p с пороговой функцией 1/n являются планарными с вероятностью 1, а ожидаемое значение у для них равно O(1). Кроме того, в [8] предложено эффективное распараллеливание алгоритма на базе модели вычислений CREW PRAM.

Для планарных орграфов получены лучшие границы. Для случая, когда стоимости ребер являются целыми числами, в [ ] предложен алгоритм с временем исполнения O(n4/3 log(nL)). В случае ребер с вещественными значениями стоимости алгоритм с временем исполнения O(n log n) можно найти в работе [5].

Для случая орграфов с малой древесной шириной (и вещественными значениями стоимости ребер) в [3] предложен оптимальный алгоритм с временем исполнения O(n). Неформально древесная ширина t графа G представляет собой параметр, измеряющий, насколько структура G близка к структуре дерева. К примеру, класс графов с малой древесной шириной включает серийно-параллельные графы (t = 2) и внешнепланарные графы (t = 2). Оптимальный параллельный алгоритм решения той же задачи на базе модели вычислений CREW PRAM был предложен в [2].

Применение

Нахождение отрицательных циклов в орграфах представляет собой фундаментальную задачу комбинаторной и сетевой оптимизации, охватывающую широкий спектр приложений, включая следующие: нахождение кратчайшего пути, элементов двумерной упаковки, потоков минимальной стоимости, минимального соотношения стоимости и времени, а также верификация модели, создание компиляторов, разработка программного обеспечения, проектирование СБИС, планирование, производство интегральных схем, программирование с учетом ограничений и обработка изображений. Скажем, изоляция циклов отрицательной обратной связи исключительно важна при проектировании СБИС. Оказывается, такие циклы соответствуют циклам с отрицательной стоимостью в так называемом «графе коэффициентов усиления» схемы. В процессе программирования с учетом ограничений необходимо проверять применимость множеств ограничений. Системы разностных ограничений могут быть представлены в виде графов ограничений, и можно показать, что такая система является применимой в том и только том случае, если в соответствующем графе ограничений не имеется циклов с отрицательной стоимостью. В планировании с нулевым уровнем предварительных знаний задача определения того факта, существует ли для данной системы достоверный план, может быть сведена к нахождению отрицательных циклов в соответствующим образом определенном графе. Дополнительную информацию об этом и других вариантах применения можно найти в [1, 12, 14].

Открытые вопросы

Задача нахождения отрицательного циклв тесно связана с задачей нахождения кратчайшего пути. Существование отрицательных стоимостей ребер делает решение задачи нахождения отрицательных циклов или вычисления дерева кратчайших путей более сложной и требует больше времени по сравнению с решением задачи нахождения дерева кратчайших путей в орграфах с неотрицательными стоимостями ребер. В качестве примера можно рассмотреть орграфы с вещественными стоимостями ребер и сравним алгоритм с временем исполнения O(nm) для первого случая с алгоритмом с временем O(m + nlog n) для второго (алгоритмом Дейкстры, реализованным с эффективной очередью с приоритетами; см., например, [1]).

Таким образом, представляет интерес сокращение разрыва между двумя указанными значениями временной сложности – даже для специальных классов графов или случая с целочисленными стоимостями ребер. Единственный случай, когда обе временные сложности совпадают, касается орграфов с малой древесной шириной [ ]; в результате этот класс графов в настоящий момент является классом самого общего вида. Для планарных орграфов результат, приведенный в [3], только на полилогарифмический коэффициент отличается от алгоритма с временем исполнения O(n), вычисляющего дерево кратчайших путей в случае неотрицательной стоимости ребер.

Экспериментальные результаты

Экспериментальное исследование задачи нахождения отрицательных циклов было проведено в [ ]; были использованы несколько методов, сочетающих алгоритм нахождения кратчайших путей (на основе подхода Беллмана-Форда) со стратегией обнаружения циклов, а также их более поздние разновидности. Оказалось, что эффективность работы алгоритмов нахождения отрицательных циклов зависит от количества и размера отрицательных циклов. В результате был получен набор семейств начальных условий для тестирования алгоритмов нахождения отрицательных циклов.

Продолжение данного исследования было опубликовано в работе [14]; в нем были представлены две новые эвристики, встроенные в три алгоритма, рассматривавшихся в [ 4 ] (исходный алгоритм Беллмана-Форда и его вариации, предложенные в [13] и [7]), что привело к значительному улучшению результатов. В [14] использовались те же наборы данных, что и в [4].

Наборы данных

Генераторы наборов данных и семейств начальных условий описаны в работе [4] и доступны на сайте http://www.avglab.com/ andrew/soft.html. Там же доступен код, используемый в [ ].

См. также

• Алгоритм поиска кратчайших путей в разреженных графах
• Алгоритм поиска кратчайших путей при помощи матричного произведения
• Алгоритм поиска кратчайших путей с единственным источником

Литература

1. Ahuja, R., Magnanti, T., Orlin, J.: Network Flows. Prentice-Hall, Englewood Cliffs (1993)

2. Chaudhuri, S., Zaroliagis, C.: Shortest Paths in Digraphs of Small Treewidth. Part II: Optimal Parallel Algorithms.Theor. Comput. Sci. 203(2), pp. 205-223 (1998)

3. Chaudhuri, S., Zaroliagis, C.: Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms. Algorithmca 27(3), pp. 212-226 (2000)

4. Cherkassky, B.V., Goldberg, A.V.: Negative-Cycle Detection Algorithms. Math. Program. 85, pp. 277-311 (1999)

5. Fakcharoenphol, J., Rao, S.: Planar Graphs, Negative Weight Edges, Shortest Paths, and near Linear Time. In: Proc.42nd IEEE Symp. on Foundations of Computer Science - FOCS (2001), pp. 232-241. IEEE Computer Society Press, Los Alamitos (2001)

6. Goldberg, A.V.: Scaling Algorithms for the Shortest Paths Problem. SIAM J. Comput. 24, pp. 494-504 (1995)

7. Goldberg, A.V., Radzik, T.: A Heuristic Improvement of the Bellman-Ford Algorithm. Appl. Math. Lett. 6(3), pp. 3-6 (1993)

8. Kavvadias, D., Pantziou, G., Spirakis, P., Zaroliagis, C.: Efficient Sequential and Parallel Algorithms for the Negative Cycle Problem. In: Algorithms and Computation - ISAAC’94. Lect. Notes Comput. Sci., vol. 834, pp.270-278. Springer, Heidelberg (1994)

9. Klein, P., Rao, S., Rauch, M., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 5(1), pp. 3-23(1997)

10. Kolliopoulos, S.G., Stein, C.: Finding Real-Valued Single-Source Shortest Paths in o(n3) Expected Time. J. Algorithms 28, pp. 125-141 (1998)

11. Mehlhorn, K., Naher, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999)

12. Spirakis, P., Tsakalidis, A.: A Very Fast, Practical Algorithm for Finding a Negative Cycle in a Digraph. In Proc. of 13th ICALP, pp. 397-406(1986)

13. Tarjan, R.E.: Data Structures and Network Algorithms. SIAM, Philadelphia (1983)

14. Wong, C.H., Tam, Y.C.: Negative Cycle Detection Problem. In: Algorithms - ESA 2005. Lecture Notes in Computer Science, vol. 3669, pp. 652-663. Springer, Heidelberg (2005)