Отрицательные циклы во взвешенных орграфах
Постановка задачи
Пусть G = (V, E) – ориентированный граф (орграф), имеющий m ребер и n вершин, ребра которого ассоциированы с вещественной стоимостной функцией [math]\displaystyle{ wt: E \rightarrow \mathbb{R} \; }[/math]. Стоимость, 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 не содержат отрицательного цикла. Для случая, когда стоимости дуг являются целыми числами не менее [math]\displaystyle{ - L (L \ge 2) \; }[/math], в [6] предложен более оптимальный алгоритм, выполняющийся за время [math]\displaystyle{ O(m \sqrt{n} log \; L) }[/math] и основанный на битовом масштабировании.
Простой детерминированный алгоритм с ожидаемым временем выполнения [math]\displaystyle{ O(n^2 log \; n) }[/math] с высокой вероятностью был приведен в [10]; он предназначен для широкого класса распределений входных данных, у которых стоимости ребер выбираются случайным образом в соответствии с независимой от конечных точек моделью (эта модель включает общий случай, при котором все стоимости ребер выбираются независимым образом из одного и того же распределения).
Лучшие результаты были получены для нескольких важных классов разреженных орграфов (т.е. орграфов, имеющих m = O(n) ребер) – таких как планарные и внешнепланарные орграфы, орграфы малого рода и малой древесной ширины.
Для разреженных орграфов общего вида в [8] был предложен алгоритм для решения задачи нахождения отрицательного цикла за время [math]\displaystyle{ O(n + \tilde{ \gamma } ^{1.5} log \; \tilde{ \gamma } ) }[/math], где [math]\displaystyle{ \tilde{ \gamma } \; }[/math] – топологическая мера входного разреженного орграфа G, значение которой меняется от 1 до [math]\displaystyle{ \Theta (n) \; }[/math]. Неформально [math]\displaystyle{ \tilde{ \gamma } \; }[/math] представляет минимальное количество внешнепланарных подграфов, удовлетворяющих определенным свойствам отделимости и полученных в результате декомпозиции графа G. В частности, [math]\displaystyle{ \tilde{ \gamma } \; }[/math] пропорционально [math]\displaystyle{ \gamma (G) + q \; }[/math], где G предполагается вложенным в ориентируемую поверхность рода [math]\displaystyle{ \gamma (G) \; }[/math] таким образом, чтобы минимизировать количество q граней, совместно покрывающих все вершины. Например, если граф G является внешнепланарным, то [math]\displaystyle{ \tilde{ \gamma } = 1 \; }[/math], в результате для такого случая получаем оптимальный алгоритм с временем выполнения O(n). Алгоритм в [8] не требует необходимого наличия такого вложения входного графа. В той же статье показано, что случайные графы [math]\displaystyle{ G_{n,p} \; }[/math] с пороговой функцией 1/n являются планарными с вероятностью 1, а ожидаемое значение [math]\displaystyle{ \tilde{ \gamma } \; }[/math] для них равно O(1). Кроме того, в [8] предложено эффективное распараллеливание алгоритма на базе модели вычислений CREW PRAM.
Для планарных орграфов получены лучшие границы. Для случая, когда стоимости ребер являются целыми числами, в [9] предложен алгоритм с временем выполнения [math]\displaystyle{ O(n^{4/3} \; log (nL)) }[/math]. В случае ребер с вещественными значениями стоимости алгоритм с временем выполнения [math]\displaystyle{ O(n \; log^3 \; n) }[/math] можно найти в работе [5].
Для случая орграфов с малой древесной шириной (и вещественными значениями стоимости ребер) в [3] предложен оптимальный алгоритм с временем выполнения O(n). Неформально древесная ширина t графа G представляет собой параметр, измеряющий, насколько структура G близка к структуре дерева. К примеру, класс графов с малой древесной шириной включает серийно-параллельные графы (t = 2) и внешнепланарные графы (t = 2). Оптимальный параллельный алгоритм решения той же задачи на базе модели вычислений CREW PRAM был предложен в [2].
Применение
Нахождение отрицательных циклов в орграфах представляет собой фундаментальную задачу комбинаторной и сетевой оптимизации, охватывающую широкий спектр приложений, включая следующие: нахождение кратчайшего пути, элементов двумерной упаковки, потоков минимальной стоимости, минимального соотношения стоимости и времени, а также верификация модели, создание компиляторов, разработка программного обеспечения, проектирование СБИС, планирование, производство интегральных схем, программирование с учетом ограничений и обработка изображений. Скажем, изоляция циклов отрицательной обратной связи исключительно важна при проектировании СБИС. Оказывается, такие циклы соответствуют циклам с отрицательной стоимостью в так называемом «графе коэффициентов усиления» схемы. В процессе программирования с учетом ограничений необходимо проверять применимость множеств ограничений. Системы разностных ограничений могут быть представлены в виде графов ограничений, и можно показать, что такая система является применимой в том и только том случае, если в соответствующем графе ограничений не имеется циклов с отрицательной стоимостью. В планировании с нулевым уровнем предварительных знаний задача определения того факта, существует ли для данной системы планирования достоверный план, может быть сведена к нахождению отрицательных циклов в соответствующим образом определенном графе. Дополнительную информацию об этом и других вариантах применения можно найти в [1, 12, 14].
Открытые вопросы
Задача нахождения отрицательных циклов тесно связана с задачей нахождения кратчайшего пути. Существование отрицательных стоимостей ребер делает решение задачи нахождения отрицательных циклов или вычисления дерева кратчайших путей более сложной и требует больше времени по сравнению с решением задачи нахождения дерева кратчайших путей в орграфах с неотрицательными стоимостями ребер. В качестве примера можно рассмотреть орграфы с вещественными стоимостями ребер и сравнить алгоритм с временем выполнения O(nm) для первого случая с алгоритмом с временем O(m + n log n) для второго (алгоритмом Дейкстры, реализованным с эффективной очередью с приоритетами; см., например, [1]).
Таким образом, представляет интерес сокращение разрыва между двумя указанными значениями временной сложности – даже для специальных классов графов или случая с целочисленными стоимостями ребер.
Единственный случай, когда обе временные сложности совпадают, касается орграфов с малой древесной шириной [3]; в результате этот класс графов в настоящий момент является классом самого общего вида. Для планарных орграфов результат, приведенный в [3], только на полилогарифмический коэффициент отличается от алгоритма с временем выполнения O(n), вычисляющего дерево кратчайших путей в случае неотрицательной стоимости ребер.
Экспериментальные результаты
Экспериментальное исследование задачи нахождения отрицательных циклов было проведено в [4]; были использованы несколько методов, сочетающих алгоритм нахождения кратчайших путей (на основе подхода Беллмана-Форда) со стратегией обнаружения циклов, а также их более поздние разновидности. Оказалось, что эффективность работы алгоритмов нахождения отрицательных циклов зависит от количества и размера отрицательных циклов. В результате был получен набор семейств начальных условий для тестирования алгоритмов нахождения отрицательных циклов.
Продолжение данного исследования было опубликовано в работе [14]; в нем были представлены две новые эвристики, встроенные в три алгоритма, рассматривавшихся в [4] (исходный алгоритм Беллмана-Форда и его вариации, предложенные в [13] и [7]), что привело к значительному улучшению результатов. В [14] использовались те же наборы данных, что и в [4].
Наборы данных и ссылка на код
Генераторы наборов данных и семейств начальных условий описаны в работе [4] и доступны на сайте http://www.avglab.com/ andrew/soft.html. Там же доступен код, используемый в [4].
См. также
Литература
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)
